Torre de hanoi

Torre de Hanoi
Interessante passatempo que surgiu no fim do século XIV, onde até hoje as pessoas se divertem com este jogo. Ele é formado com uma base de três pinos e vários discos de raios diferentes.

O problema consiste em passar todos os discos de um pino para outro qualquer, usando um dos pinos como auxiliar, obedecendo às seguintes regras: * Nunca colocar um disco maior sobre um disco menor; * Pode-se mover um único disco por vez; * Nunca colocar um disco noutro lugar que não seja um dos três pinos.
É 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 4 discos, são necessários no mínimo 15 movimentos; * Para solucionar um Hanói de 7 discos, são necessários no mínimo 127 movimentos; * Para solucionar um Hanói de 15 discos, são necessários no mínimo 32.767 movimentos; * Para solucionar um Hanói de 64 discos, como diz a lenda, são necessários no mínimo 18.446.744.073.709.551.615 movimentos.

Algoritmo Guloso
Os algoritmos gulosos tomam decisões com base apenas na informação disponível, sem se preocupar com os efeitos futuros de tais decisões, isto é, eles nunca reconsideram as decisões tomadas, independentemente das conseqüências. Não há, portanto, necessidade de avaliar as alternativas nem de empregar procedimentos elaborados permitindo que decisões anteriores sejam desfeitas. Devido a tais características, de forma geral eles são fáceis de “inventar” e implementar, e são eficientes quando funcionam.
A partir de uma seqüência de escolhas, um algoritmo guloso busca encontrar a solução ótima para o problema em questão. Conforme exposto, a estratégia utilizada é em cada passo escolher a solução que parece ser a melhor.
No entanto, nem sempre um algoritmo guloso consegue resolver um problema de otimização. Mas existem duas características que podem indicar que os problemas podem