A torre de Hanói, também conhecida por torre de bramanismo ou quebra-cabeças do fim do mundo, foi inventada e vendida como brinquedo, no ano de 1883, pelo matemático francês François Édouard Anatole Lucas. Um dos maiores matemáticos da história, nasceu em 04 de abril de 1842 em Amiens, França, e morreu em 03 de outubro de 1891, em Paris. Foi ele que estudou e desenvolveu a famosa fórmula matemática de Fibonacci, conhecida como Seqüência de Fibonacci. Seus estudos nesta área são conhecidos como Seqüência de Lucas, ele elaborou a fórmula para encontrar o termo n elevado a th da Seqüência de Fibonacci. Foi educado na École Normale Supérieure. Trabalhou no Observatório de Paris e posteriormente foi professor de matemática em escolas e universidades francesas. É 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 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.

■ Aplicação Prática

A Torre de Hanói pode ser trabalhada em níveis de desenvolvimento com crianças. Na pré-escola, com regras simples de separação de cores e tamanhos, a torre de Hanoi ajuda em questões de coordenação motora, identificação de formas, ordem crescente e decrescente, entre outras formas de aprendizado.

De uma maneira mais ampla, o jogo pode ser usado para o estabelecimento de estratégias de transferência das peças, como a contagem dos movimentos e raciocínio.

Iniciando com um número menor de peças, ou seja, resolvendo problemas mais simples, teremos oportunidade de experimentar uma das mais importantes formas de raciocínio matemático.

■ Conclusão

A Torre de Hanoi consiste em passar todos os discos de uma extremidade a outra sem que um disco maior fique em cima de um menor.

As suas aplicações são basicamente usadas em escolas para que os professores possam melhorar e desenvolver o cognitivo das crianças, além do trabalho em grupo. Sendo este aplicado em pequenos grupos ou individualmente.

A Torre de Hanoi possui várias formas de resolução. Uma delas é a resolução recursiva a qual podemos dizer que é a mais limitada quanto ao tempo de realização, já que sua execução dependerá de alguns fatores para tornar-se mais eficaz.

A resolução Iterativa utiliza alguns ciclos (estruturas) de repetição (for, whiles) que podem ser chamados de laços, existe ainda a possibilidade de algumas estruturas adicionais (mais complexas) as quais tornam o algoritmo mais rápido.

É fato que todo algoritmo recursivo possuí um algoritmo iterativo equivalente, dependendo apenas da sua complexidade de construção.

■ Soluções

É interessante observar que o número mínimo de "movimentos" para conseguir transferir todos os discos da primeira estaca à terceira é 2ⁿ-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 32.767 movimentos.

Para solucionar um Hanoi de 64 discos, são necessários 18.446.744.073.709.551.615 movimentos.

 

► Para ver a funcionalidade do algoritmo escolha abaixo as opções e depois clique na opção "Iniciar". ◄

 

Número de discos:	Random 1 2 3 4 5 6 7 8
Tempo do Movimento:	100 milliseconds 200 milliseconds 300 milliseconds 400 milliseconds 500 milliseconds 600 milliseconds 700 milliseconds 800 milliseconds 900 milliseconds 1000 milliseconds

 - 

 

■ Algoritmo

A solução para o problema da Torre de Hanoi com recursividade é compacta e baseia-se no seguinte:

    a) A única operação possível de ser executada é "move disco de um pino para outro";

    b) Uma torre com (N) discos, em um pino, pode ser reduzido ao disco de baixo e a torre de cima com (N-1) discos;

    c) A solução consiste em transferir a torre com (N-1) discos do pino origem para o pino auxiliar, mover o disco de baixo do pino origem para o pino destino e transferir a torre com (N-1) discos do pino auxiliar para o pino destino. Como a transferência da torre de cima não é uma operação possível de ser executada, ela deverá ser reduzida sucessivamente até transformar-se em um movimento de disco.

Fig. Solução com o disco de baixo e a torre de cima

 

O algoritmo deve ser especificado, através de um módulo (procedimento) que pode chamar a si mesmo, consistindo do seguinte:

se N=1

  então move disco da origem para o destino

  senão início

        TRANSFERE (N-1, origem, auxiliar, destino)

        move disco de origem para o destino

        TRANSFERE (N-1, auxiliar, destino, origem)

   fim

 

 ► Clique aqui agora para você poder praticar sua capacidade lógica ◄