Ajude os monges de Hanói com suas torres
Existe uma lenda de que, perto da cidade de Hanói, no Vietnã, há um mosteiro com uma placa de bronze e três hastes sobre ela.
Na criação do mundo, Deus enfiou 64 discos de vários diâmetros, feitos de ouro puro, na primeira haste. Ele colocou o maior disco sobre a placa e colocou cada disco menor sobre um maior.
Havia uma profecia de que, no momento em que os monges do mosteiro transferissem todos esses 64 discos da primeira haste para a terceira, o fim do mundo chegaria e a felicidade eterna chegaria para os justos. Por isso, os monges trabalham dia e noite, transportando discos. Mas o trabalho avança muito lentamente porque os monges precisam seguir duas regras simples:
- Os discos podem ser movidos de uma haste para outra, um de cada vez.
- Os monges não podem colocar um disco maior sobre um menor.
Os monges receberam um prazo de 600 bilhões de anos para concluir seu trabalho. Mas já estão atrasados porque às vezes se perdem nos cálculos e, por muito tempo, não conseguem decidir qual disco mover e para onde.
Ajude os monges. Escreva uma função que, ao receber o número do movimento, mostre como realizar esse movimento. A função deve retornar uma tupla de três números:
- Número do disco.
- Número da haste de onde retirar o disco.
- Número da haste onde colocar este disco.
Os discos são numerados de 1 (o menor disco) a 64 (o maior disco).
Exemplos
hanoi(1) ➞ (1, 1, 2)
hanoi(2) ➞ (2, 1, 3)
hanoi(2**63) ➞ (64, 1, 3)
hanoi(15215285751613538304) ➞ (15, 2, 3)Notas
Em um computador comum, o Python levaria cerca de 50 mil anos para realizar todos os movimentos dos discos. Portanto, em vez de percorrer todos os movimentos, é necessário encontrar um padrão de movimentos.
