Por 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.
0 comentários:
Postar um comentário