Torre de Hanói (Tower of Hanoi)

1. Introução
2. Abordagem
3. Algoritmo
4. Tipos Abstratos de Dados
5. Cáculos e Complexidades
6. Dicionário de variáveis.
7. Outros

---

1. INTRODUÇÃO

"A Torre de Hanói é um jogo ou quebra-cabeça matemático. É composto por três hastes e um número de discos de tamanhos diferentes, que podem deslizar para qualquer haste. O quebra-cabeça começa com os discos em uma pilha organizada em ordem crescente de tamanho em uma haste, a menor na parte superior, criando assim uma forma cônica." Wikipédia

---

2. ABORDAGEM

Usar as hastes da torre como uma pillha, e uma árvore binária perfeita implementada como um vetor para armazenar as movimentações dos discos, onde cada nó da árvore é um par ordenado (a, b), tal que "a" é o índice da haste de origem e "b" o índece da haste de destino. Sendo cada nível da árvore representando um disco(Separado por cores na figura abaixo).

---

3. ALGORITMO

O algoritmo consiste em:

• Criar três pillhas para representar as hastes.
• Criar "N" discos, onde inicialmente são colocados em ordem crescente do topo até a base da primeira haste.
• Criar uma árvore binária perfeita sendo a quantidade de níveis da árvore igual a quantidade de discos.
• Preencher os nós por nível, onde o nó inical de cada nível consiste no índice da primeira haste e o índice da haste vizinha, denominados "origem" e "destino".
  E o nó seguinte de mesmo nível é prenchido com o índice de destino do nó anterior e o índice da haste vizinha.
• A vizinhança segue uma rotação modular dos índices das hastes, que alternam no sentido horário e anti-horário por nível da árvore, sendo o primeiro nível no sentido anti-horário.
• Faz uma varredura em ordem dos nós da arvore e movendo os discos da haste de origem para a haste de destino conforme armazenado no preenchimento dos nós.
• Após a vareedura todos os discos estarão em ordem crescente do topo até a base da na ultima haste.

---

4. Tipos Abstratos de Dados TAD

4.1. Perfect Binary Tree

"Na ciência da computação, uma árvore binária é uma estrutura de dados de árvore na qual cada nó tem no máximo dois filhos, chamados de filho esquerdo e filho certo. Uma definição recursiva usando apenas noções de teoria dos conjuntos é que uma árvore binária (não vazia) é uma tupla (L, S, R), onde L e R são árvores binárias ou o conjunto vazio e S é um conjunto unitário" Wipédia

"Uma árvore binária perfeita é uma árvore binária na qual todos os nós internos têm dois filhos e todas as folhas têm a mesma profundidade ou mesmo nível." Wikipédia

4.2. Array

"As árvores binárias também podem ser armazenadas em ordem de largura como uma estrutura de dados implícita em matrizes e, se a árvore for uma árvore binária completa, esse método não desperdiçará espaço. Nesse arranjo compacto, se um nó tem um índice i, seus filhos são encontrados nos índices 2i + 1 (para o filho esquerdo) e 2i + 2 (para o direito), enquanto seu pai (se houver) é encontrado no índice (i-1)/2 (assumindo que a raiz tenha o índice zero).Wikipédia"

4.3. Pair

Uma tupla de dois elementos inteiros formando um par ordenad (a, b). Wikipédia

4.4. Stack

*"Na ciência da computação, uma pilha é um tipo abstrato de dados que serve como uma coleção de elementos, com duas operações principais:

• push, que adiciona um elemento à coleção e
• pop, que remove o elemento adicionado mais recentemente que ainda não foi removido.

A ordem na qual os elementos saem de uma pilha dá origem ao seu nome alternativo, LIFO (Last In, First Out [último a entrar, primeiro a sair]). Além disso, uma operação de peek pode dar acesso ao topo sem modificar a pilha. O nome "pilha" para esse tipo de estrutura vem da analogia com um conjunto de itens físicos empilhados uns sobre os outros, o que facilita tirar um item do topo da pilha, enquanto obtenção de um item mais profundo na pilha pode exigir a retirada de vários outros itens."Wikipedia*

---

Task List

• Cria vetor de pilhas representando as hastes
• Transformar árvore binária perfeita em um vetor
• - Criar função de aritmética modular
• Criar função para inicializar a árvore
• - Criar função matemática anternante para horário e anti-horário.
• - Preencher por níveis a árvore usando a função alternante
• Criar funções para nós da árvore
• - Pai
• - Filho esquerdo
• - Filho direito
• Criar função iterativa EM Ordem para percorrer a árvore
• Criar função para mover os discos entre as hastes
• Criar modo gráfico em formato de texto (terminal)
• Criar modo gráfico em formato OpenGL