Torre de Hanói

A LENDA

Conta a lenda que no tempo de Benares, sob a cúpula que marcava o centro do mundo, existia uma bandeja de bronze com três agulhas de diamantes, cada uma de um palmo de altura e da grossura do corpo de uma abelha.
Durante a Criação, Deus colocou 64 discos de ouro puro em uma das agulhas, o maior deles imediatamente acima da bandeja e os demais, cada vez menores, por cima. Esta torre foi chamada de Torre de Brahma.
Dia e noite, incessantemente, os sacerdotes trocavam os discos de uma agulha para a outra, de acordo com as leis imutáveis de Brahma, que dizia que o sacerdote do turno não poderia mover mais que um disco de cada vez, e que o disco fosse colocado na outra agulha, de maneira que o debaixo nunca fosse menor do que o de cima.
Quando todos os 64 discos tivessem sido transferidos da agulha que Deus colocou no dia da Criação para outra agulha, o mundo deixaria de existir.

O PROBLEMA

A Torre de Hanói foi inventada em 1883 pelo francês Edouard Lucas. No problema existem 3 pinos e n discos, sendo que estes discos são dispostos de forma crescente de baixo para cima em um dos pinos. O objetivo é transferir todos os discos do primeiro pino para outro pino, de forma que estes fiquem dispostos como originalmente e que se respeite duas regras básicas: a primeira é que só se pode movimentar 1 disco por vez, a segunda é que não se pode colocar um disco maior por cima de um menor.

A PERGUNTA

Qual o número mínimo de movimentos que são necessários para resolver o problema com n discos?

O DESAFIO

Crie o algoritmo para a resolução da Torre de Hanói com qualquer número de discos.