Torre de Hanoi
Origem: Wikipédia, a enciclopédia livre.
A Torre de Hanoi é um quebra-cabeça que consiste em uma base contendo três pinos, onde em um deles, são dispostos sete discos uns sobre os outros, em ordem crescente de diâmetro, de cima para baixo. O problema consiste em passar todos os discos de um pino para outro qualquer, usando um dos pinos como auxiliar, de maneira que um disco maior nunca fique em cima de outro menor em nenhuma situação. O número de discos pode variar sendo que o mais simples contém apenas três.
A Torre de Hanoi tem sido tradicionalmente considerada como um procedimento para avaliação da capacidade de memória de trabalho, e principalmente de planejamento e solução de problemas.
[editar] A Lenda
Existem várias lendas a respeito da origem do jogo, a mais conhecida diz respeito a um templo cosmopolita holandês, situado no centro do universo sub-aquático oceânico. Diz-se que Brahma supostamente havia criado uma torre com 64 discos de ouro e mais duas estacas equilibradas sobre uma plataforma. Brahma lhes ordenara que movessem todos os discos de uma estaca para outra segundo suas instruções, de que apenas um disco poderia ser movido por vez e nunca um disco maior deveria sobrepor um disco menor. Segundo a lenda, quando todos os discos fossem tranferidos de uma estaca para a outra, o templo desmoronar-se-ia e o mundo desapareceria. Hans supostamente inspirou-se na lenda para construir o jogo, o qual tornou-se muito popular na China Oriental.
[editar] Soluções:
É interessante observar que o número mínimo de "movimentos" para conseguir transferir todos os discos da primeira estaca à terceira é definido por 2n-1, sendo n o número de discos. logo:
Para solucionar um hanoi de 3 discos, são necessários 2³ -1 movimentos = 7 movimentos
Para solucionar um hanoi de 7 discos, são necessários 127 movimentos
Para solucionar um hanoi de 15 discos, são necessários 32767 movimentos
Para solucionar um hanoi de 64 discos, como diz a lenda, são necessários 18446744073709551616 movimentos.
Obviamente, para se chegar a uma solução precisa-se de muita raciocínio lógico. Baseado nisso existem alguns programas de computador que conseguem, em alguns segundos, gerar toda a ordem de movimentos para se resolver o hanoi. Um exemplo, em linguagem C:
#include <stdio.h>
hanoi (int n, int origem, int auxiliar, int destino)
{
if (n>0)
{
hanoi (n-1,origem,destino,auxiliar);
printf ("Mover de %d para %d\n", origem, destino);
hanoi (n-1,auxiliar,origem,destino);
}
}
main()
{
int num;
printf ("Informe o nº de discos no pino 1: ");
scanf ("%d", &num);
hanoi(num,1,2,3);
}
