Trabalho Final de Estrutura de Dados
Voltar para Estrutura de Dados
Problema: Torre de Hanoi
Existem várias lendas a respeito da origem do jogo, a mais conhecida diz respeito a um templo Hindu, situado no centro do universo. Diz-se que Brahma supostamente havia criado uma torre com 64 discos de ouro e mais duas estacas equilibradas sobre uma plataforma. Brahma ordenara-lhes que movessem todos os discos de uma estaca para outra segundo as suas instruções. As regras eram simples: apenas um disco poderia ser movido por vez e nunca um disco maior deveria ficar por cima de um disco menor. Segundo a lenda, quando todos os discos fossem transferidos de uma estaca para a outra, o templo desmoronar-se-ia e o mundo desapareceria.
Estado inicial
No caso desse trabalho, usaremos apenas 3 discos. Também consideraremos que o pino a esquerda é o pino A, o pino central é o B e o C é o pino a direita. Por fim, temos três discos, o pequeno, o médio e o grande.
- Inicia-se com todos os discos empilhados no pino A. O Grande em baixo, o médio em cima do grande e por cima de todos o pequeno.
Trabalho
Implementar um programa que resolve o problema da Torre de Hanoi, movendo todos os discos do pino A para o pino B.
Para isso, deve-se
- Implementar uma pilha para ser utilizada para representar os pinos A, B e C.
- Implementar uma árvore n-ária para conter as opções possíveis de movimentação dos discos de um pino para o outro.
- Encontrar na árvore n-ária uma solução para a resolução da torre de hanoi e implementar uma lista para encontrar um caminho feito de cada estado, passos ou movimentação dos discos nos pinos, do estado inicial até a solução.
- A árvore vai sendo criada recursivamente, quando o nó destino for encontrado, é criada uma lista, fazendo um backtracking do nó destino até o nó origem, armazenando essas informações em uma lista. Essa lista é retornada como resultado, não precisando mais da árvore para conter as informações.
Considere as seguintes restrições
- Nenhum disco pode estar sobre um disco melhor;
- Apenas um disco pode ser movido por vez, e sempre que ele for retirado de um pino, deve ser colocado em outro para que outra operação possa ocorrer;
- Uma pilha pode ter apenas as seguintes operações:
- Colocar um elemento no topo;
- Ver qual elemento está no topo;
- Retirar o elemento do topo.
- Em um alista, pode-se adicionar ou retirar elemento de qualquer parte, pode-se navegar do início para o fim e do fim para o início.
