Subscribe Twitter Facebook

sexta-feira, 17 de dezembro de 2010

Torre de Hanói - Interessante Quebra-cabeça matemático


A Torre de Hanói é um quebra-cabeça que consiste em uma base contendo três pinos, em um dos quais são dispostos alguns 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 Hanói 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.

                                                 Um Modelo das Torres de Hanoi

Edouard Lucas, matemático francês, teve inspiração de uma lenda para construir o jogo das Torres de Hanói. Já seu nome foi inspirado na torre símbolo da cidade de Hanói, no Vietnã.
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.
 
É interessante observar que o número mínimo de "movimentos" para conseguir transferir todos os discos da primeira estaca à terceira é 2n-1, sendo n o número de discos. Logo:
Para solucionar um Hanói de 4 discos, são necessários 15 movimentos
Para solucionar um Hanói de 7 discos, são necessários 127 movimentos
Para solucionar um Hanói de 15 discos, são necessários 32.767 movimentos
Para solucionar um Hanói de 64 discos, como diz a lenda, são necessários 18.446.744.073.709.551.615 movimentos.
Para entender a lógica da Torre de Hanói é necessário analisar a construção de diferentes níveis da torre com o número mínimo de movimentos, tendo o nível anterior já formado, sendo que esses níveis são o número de peças desintegradas da torre original que irão formar outra torre com os menores discos.
Para mover o primeiro disco da torre original, 1 movimento é gasto. Para mover o segundo da torre original, sendo que o primeiro já foi movido e será construída uma torre com os 2 menores discos, são gastos 2 movimentos. Para deslocar o terceiro disco formando nova torre com os três menores discos, tendo a torre com os dois menores já formada, são gastos 4 movimentos.
Assim se sucede com os próximos discos até que o enésimo disco (o último) seja deslocado compondo uma torre com os outros discos tendo uma torre com o penúltimo disco e os demais juntos já formada. A sucessão formada pela soma dos movimentos é uma sucessão (1,2,4,8...2n)
A fórmula 2n − 1 é provinda da soma de uma progressão geométrica.
Sabe-se que em uma progressão geométrica a soma de seus termos equivale a [a * (qn − 1)] / q − 1, onde "a" é o primeiro termo e "q" é a razão.
Já que a razão é 2 e o primeiro termo é 1 temos que [a * (qn − 1)] / q − 1 = [1 * (2n − 1)] / 2 − 1 = 2n − 1
  
Fonte: Wikipédia

Para jogar e se divertir, clique aqui 


Instruções para o jogo: O jogo da Torre de Hanói tem três pólos. No primeiro pólo existe alguns discos com diferentes dimensões ordenados do maior para o menor.
As regras do jogo são muito simples. Você precisa mover um disco de cada vez, mas sabendo que um disco maior não pode ser posto em cima de um menor.
À esquerda você pode escolher o nível de dificuldade que é o número de discos que você quer usar. Escolha de 1 a 8, e, para começar o jogo, aperte o botão START.
O propósito do jogo é mover todos os discos para o último pólo e reconstruir a torre exatamente como ela era antes.
Para mover um disco, pressione o botão esquerdo do mouse sobre ele e arraste-o até o topo da próxima torre, e solte o botão do mouse. Se você fizer um movimento válido, o disco vai cair automaticamente. Do contrário, ele vai voltar para sua possição original.

0 comentários: