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.