RVA - Torre de Hanoi

Algoritmo

Torre de Hanoi

(Hanoi Tower)

Algorítmo da Torre de  Hanoi
Claudio Kirner - 2007

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.

A Fig. 1 mostra os passos da solução com o disco de baixo e a torre de cima. Para mover a torre de cima, aplica-se novamente a solução com o disco de baixo dessa torre e a subtorre de cima, e assim por diante até sobrar só um disco, que poderá ser movido. Isto liberará a movimentação dos outros discos de baixo, que ficaram pendentes, constituindo uma solução recursiva.



Fig. 1 - Solução da Torre de hanoi com o disco de baixo e a torre de cima.

Embora os pinos sejam fixos, eles assumem papeis de origem, destino e auxiliar diferentes, em cada passo, conforme indicam as cores.  
O algoritmo pode ser especificado, através de um módulo (procedimento) que pode chamar a si mesmo (recursivo), consistindo do seguinte:



Fig. 2 - Algoritmo recursivo da Torre de Hanoi

Se o programa principal for executado para uma torre de um único disco, ele simplesmente moverá o disco da origem para o destino e finalizará.
Por outro lado, o programa principal, ao ser executado para uma torre com um número de discos maior que um, chamaráo módulo “TRANSFERE”, que fará, inicialmente, a transferência da torre de cima (N-1 discos) situada no pino origem para o pino auxiliar, conforme os parâmetros da Fig. 2 e o diagrama da Fig. 1. Depois, moverá o disco de baixo da origem para o destino. Finalmente, chamará de novo o módulo “TRANSFERE”, que fará a transferência da torre de cima (N-1 discos) situada no pino auxiliar para o pino destino, terminando o programa.