Torres de Hanoi é um quebra-cabeça que consiste em uma base contendo três pinos (pino 1, pino 2 e pino 3), onde no pino 1 são dispostos alguns discos empilhados, em ordem crescente de diâmetro (o maior embaixo). O problema consiste em passar todos os discos do pino 1 para o pino 3, usando o pino 2 como auxiliar. O número de discos pode variar sendo que o mais simples contém apenas três.

Resumindo as regras:

• Somente um disco pode ser movido de cada vez;
• Nenhum disco pode ficar sobre um disco de diâmetro menor;
• Cada movimento consiste em pegar um disco de um pino e colocá-lo em outro pino;
• Só é possível em cada movimento pegar o último disco empilhado em um pino.

Implemente um programa que resolva este problema.

Qual o número mínimo de movimentos em que é possível resolver o problema de acordo com o número de pinos iniciais?