Kori - Jogos Educativos ->
Adoos
Bookmark and Share
Configuração de video a partir de 1024 X 768 pixels.

quinta-feira, 17 de julho de 2008

Torre de Hanoi

Como surgiu

A torre de Hanoi, também conhecida por torre do Bramanismo ou quebra-cabeças do fim do mundo, foi publicada em 1883 pelo matemático francês Edouard Lucas, com o pseudônimo Prof. N. Claus (de Siam), um anagrama de seu nome. A publicação dizia que o jogo vinha do Vietnã, sendo popular também na China e no Japão, e acompanhava a caixa do quebra-cabeça.

Para solucionar um hanoi de:

  • 3 discos, são necessários 2³ -1 movimentos = 7 movimentos,
  • 7 discos, são necessários 127 movimentos,
  • 15 discos, são necessários 32.767 movimentos,
A publicação também oferecia mais de um milhão de Francos para quem resolvesse o problema da Torre de Hanoi com 64 níveis, seguindo as regras do jogo, indicando que o número de movimentos seria (264 – 1), ou seja, 2 elevado a 64 menos 1 = 18.446.744.073.709.551.615 o que daria mais do que 5 bilhões de séculos, se cada movimento fosse feito em 1 segundo.

Edouard Lucas foi inspirado por uma lenda Hindu que falava de um templo em Bernares, cidade santa da Índia, onde existia uma torre sagrada do bramanismo, cuja função era melhorar a disciplina mental dos monges jovens. A lenda dizia que, no início dos tempos, foi dada aos monges de um templo uma pilha de 64 discos de ouro, dispostos em uma haste, de forma que cada disco de cima fosse menor que o de baixo. A atribuição que os monges receberam foi transferir a torre, formada pelos discos, de uma haste para outra, usando a terceira como auxiliar com as restrições de movimentar um disco por vez e de nunca colocar um disco maior sobre um menor. Os monges deveriam trabalhar com eficiência noite e dia e, quando terminassem o trabalho, o templo seria transformado em pó e o mundo acabaria.

Definição do Problema

O problema da Torre de Hanói envolve um ambiente formado por uma base, contendo 3 pinos, onde, em um deles, há uma pilha de discos furados no meio e de diâmetros diferentes ordenados de forma que o disco maior esteja em baixo e o menor esteja em cima, formando assim uma torre conforme a figura a seguir:

Solucionar um Hanoi consiste em transferir todos os discos do pino da direita para o pino da esquerda obedecendo as seguintes restrições:
  1. Só é possível movimentar um disco por vez para qualquer pino;
  2. Um disco maior nunca poderá ser colocado sobre um menor;
  3. A solução deverá ser encontrada com o menor número de passos possíveis.

2 comentários: