Torre de Hanói: número mínimo de movimentos e variante com 4 pinos
Informe o número de discos, os pinos e o tempo por movimento para ver os movimentos mínimos com 3 ou 4 pinos, o tempo total e o primeiro movimento.
- Roda no seu navegador
Resultado
O resultado aparece aqui.
Movimentos mínimos
3 pinos: M(n) = 2·M(n−1) + 1 = 2ⁿ − 1; 4 pinos (Frame-Stewart): (m − 1)·2^m + 1 + (n − T(m))·2^m, com T(m) = m(m+1)÷2 ≤ n ≤ T(m+1) − 1
Com 7 discos, a Torre de Hanói exige no mínimo 127 movimentos com 3 pinos e 25 com 4 pinos (economia de 80,3%). A 1 s por movimento, 127 movimentos levam 127 s, ou 0 dias. O primeiro movimento (3 pinos) leva o menor disco do pino A para o pino C (destino).
Crescimento exponencial
Com 40 discos em 3 pinos, são 1.099.511.627.775 movimentos: a 1 s cada, 34.841,42 anos. Cada disco a mais dobra o número de movimentos.
Sobre os 4 pinos
- Para 3 pinos, 2ⁿ − 1 é provadamente o mínimo. Para 4 pinos, o número de Frame-Stewart é o mínimo conjeturado: a conjetura de otimalidade só está provada para 3 pinos, e a página a declara como referência.
- O primeiro movimento do menor disco vai para o pino de destino se n for ímpar e para o auxiliar se n for par (3 pinos).
- A lista completa de movimentos não é gerada; a recorrência M(n) = 2·M(n−1) + 1 explica o algoritmo recursivo.
Perguntas frequentes
Quantos movimentos tem a Torre de Hanói?
Com 3 pinos e n discos, o mínimo é 2ⁿ − 1 movimentos: 7 discos pedem 127.
Qual o número de movimentos da Torre de Hanói com 5 discos?
São 31 movimentos com 3 pinos. A página dá o total e o primeiro movimento, mas não lista toda a sequência.
Como achar o número mínimo de movimentos de Hanói?
Pela recorrência M(n) = 2·M(n−1) + 1, que dá 2ⁿ − 1; com 4 pinos vale o número de Frame-Stewart.
Como usar a calculadora da Torre de Hanói?
Informe o número de discos e o tempo por movimento: a página calcula os movimentos mínimos, o tempo total e a versão com 4 pinos.