Torre de Hanói - Algoritmo

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.

É 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 3 discos, são necessários 2³ -1 movimentos = 7 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.

Algoritmo:

 

(N, origem, destino, auxiliar)
{ transfere uma torre de N discos da origem para o destino,
   usando o pino auxiliar, se for necessário   }
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