Algoritmo para solução da Torre de Hanói

A Torre de Hanói é um quebra-cabeça matemático que consiste em três hastes e um número de três ou mais discos de diferentes tamanhos para serem dispostos nas hastes. O problema está em passar todos os discos de uma haste para outra, usando uma terceira haste como auxiliar, de maneira que um disco maior nunca fique em cima de outro menor e movendo um disco por vez. O nível de dificuldade mais fácil é com três discos apenas.

O número mínimo de movimentos para conseguir transferir todos os discos da primeira haste para a haste final é 2^n -1, sendo n o número de discos. Por exemplo para solucionar uma Torre de Hanói com 7 discos são necessários 127 movimentos.

Existem soluções para este problema com o uso de algoritmos iterativos, mas geram um código muito extenso visto que algoritmos recursivos são bem mais fáceis de serem compreendidos pois são compactos. Entretanto por usarem intensivamente a pilha, os algoritmos recursivos tendem a ser mais lentos que os iterativos.

Vejamos então um exemplo de algoritmo recursivo:

Função resolveHanoi(Inteiro discos, String origem, String destino, String auxiliar) {
 Se (discos > 0) {
 resolveHanoi(discos-1,origem,auxiliar,destino);
 Imprime("Mover disco " + discos + " de " + origem + " para " + destino);
 resolveHanoi(discos-1,auxiliar,destino,origem);
 }
}

A função é chamada com:

resolveHanoi(3,"haste inicial","haste final","haste auxiliar");

Este algoritmo imprime na tela toda a seqüência de movimentos para a solução do problema. A função é chamada pela primeira vez com parâmetros determinando o número total de discos e quais são as hastes inicial, final e auxiliar.

Para a solução, os movimentos realizados pelo algoritmo estão separados em três estágios. O primeiro estágio move os n-1 discos superiores para a haste auxiliar, o segundo move o último e maior disco para a haste final e finalmente o terceiro estágio move os n-1 discos superiores para a haste final.

Com o uso da recursão, dentro do primeiro e do terceiro estágio, são realizados novamente os três estágios com a pilha de n-1 discos, avançando recursivamente sempre no primeiro e terceiro estágios até que se chegue no menor disco.

A seqüência dos discos movidos para uma torre com três discos é 1-2-1-3-1-2-1. A representação gráfica desta solução é semelhante ao Triângulo de Sierpinski, que é uma figura geométrica obtida através de um processo recursivo.

Sugestão de website: Hanoimania!