A Torre de Hanói é um quebra-cabeça clássico de lógica e um dos exemplos mais usados para ensinar recursão em programação. Jogue com 3 a 10 discos, conte seus movimentos e compare com o mínimo, ou deixe a solução automática mostrar o caminho ótimo.
Fórmula do Número Mínimo de Movimentos
| Discos | Movimentos mínimos (2ⁿ − 1) |
|---|---|
| 3 | 7 |
| 4 | 15 |
| 5 | 31 |
| 6 | 63 |
| 7 | 127 |
| 8 | 255 |
| 10 | 1.023 |
| 20 | 1.048.575 |
| 64 | 18.446.744.073.709.551.615 |
Algoritmo Recursivo
def hanoi(n, origem, destino, auxiliar):
if n == 0:
return
hanoi(n - 1, origem, auxiliar, destino)
print(f"Mova o disco {n} de {origem} para {destino}")
hanoi(n - 1, auxiliar, destino, origem)
hanoi(3, "A", "C", "B")O número de movimentos segue a recorrência T(n) = 2·T(n − 1) + 1, com T(0) = 0, cuja solução é 2ⁿ − 1. Por isso a complexidade do algoritmo é exponencial: O(2ⁿ).
Solução para 3 Discos
- A → C
- A → B
- C → B
- A → C
- B → A
- B → C
- A → C
Perguntas Frequentes
Quais são as regras da Torre de Hanói?
Mover todos os discos da primeira haste para a última, um disco por vez, sempre pegando o disco do topo, e nunca colocando um disco maior sobre um menor. A haste do meio serve de apoio.
Qual o número mínimo de movimentos?
Para n discos, o mínimo é 2ⁿ − 1. Com 3 discos são 7 movimentos, com 4 são 15, com 5 são 31, com 8 são 255 e com 10 são 1.023.
Qual a estratégia para resolver?
Pense de forma recursiva: para mover n discos de A para C, mova os n − 1 de cima para B, mova o maior para C e depois mova os n − 1 de B para C. Uma regra prática: o menor disco se move a cada dois lances, sempre no mesmo sentido circular.
O que diz a lenda da Torre de Hanói?
Conta-se que monges de um templo movem 64 discos de ouro seguindo essas regras, e que o mundo acabará quando terminarem. Com um movimento por segundo, seriam 2⁶⁴ − 1 segundos, cerca de 585 bilhões de anos. O quebra-cabeça foi criado pelo matemático francês Édouard Lucas em 1883.