inthink.guide
LojaVoltar ao início

Jogue. Preveja. Entenda.

Torre de Hanói

Jogue com 3–5 discos, peça uma dica para a posição atual e aprenda a estratégia recursiva em duas animações curtas. Abra um exemplo passo a passo quando precisar.

Jogar Torre de Hanói
ABCDisco 44Disco 33Disco 22Disco 11

Afaste a pilha pequena para liberar o maior disco.

Regras da Torre de Hanói

  1. Leve toda a pilha da coluna A para a C.
  2. Mova apenas um disco por vez, sempre o que está no topo.
  3. Nunca coloque um disco maior sobre um menor.

Jogar Torre de Hanói

Escolha a origem e depois o destino. Os números indicam o tamanho: 1 é o menor. Desfaça um movimento ou reinicie para testar outra ideia.

0 movimento
ABCDisco 33Disco 22Disco 11

Escolha a coluna de origem e depois a de destino.

As dicas usam seu tabuleiro e não movem discos por você. Um desvio dentro das regras ainda tem solução.

Como resolver a Torre de Hanói

Pense primeiro no maior disco. No exemplo de quatro discos, três pequenos o bloqueiam. Resolva esse problema menor antes de mover o disco 4.

  1. Afaste a pilha menor

    Mova os discos 1, 2 e 3 de A para B, usando C como apoio. Deixe o disco 4 em A. Agora C está livre e o disco 4 está acessível.

    ABCDisco 44Disco 33Disco 22Disco 11

  2. Mova o maior disco

    Mova o disco 4 de A para C. Esse movimento o coloca na posição final.

    ABCDisco 44Disco 33Disco 22Disco 11

  3. Leve a pilha menor ao destino

    Mova os discos 1, 2 e 3 de B para C, usando A como apoio. Eles cabem sobre o disco 4 e completam o jogo.

    ABCDisco 44Disco 33Disco 22Disco 11

Cada pilha menor segue o mesmo plano: afastar os discos acima do maior, mover esse disco e trazer a pilha menor para cima dele. Com um só disco, mova-o diretamente. Isso é recursão; origem, destino e apoio mudam em cada subproblema.

Aprenda prevendo o próximo objetivo

Estes exemplos independentes de quatro discos preservam sua partida. Pause, avance um movimento, responda à previsão ou abra a explicação.

1. Abra caminho para o maior disco

Veja três discos pequenos liberar o disco 4. Preveja onde precisam estar antes de mover o maior.

Exemplo independente com quatro discos

Objetivo: mover 3 discos de A para B, usando C como apoio.

ABCDisco 44Disco 33Disco 22Disco 11

Abra caminho primeiro: mova os três discos de cima de A para B.

Passo 0 de 8

2. Repita o problema menor

O disco 4 já está em C. Resta o mesmo problema com três discos e outras funções para as colunas.

Exemplo independente com quatro discos

Objetivo: mover 3 discos de B para C, usando A como apoio.

ABCDisco 44Disco 33Disco 22Disco 11

O disco 4 fica em C. Resolva agora os três discos de B para C.

Para mover três discos de B para C usando A, aonde o disco 1 vai primeiro?

Passo 0 de 7

Soluções passo a passo

Os exemplos começam com todos os discos em A e terminam em C. Abra qualquer um diretamente; sua partida não muda.

Número mínimo de movimentos

T(n) = 2T(n − 1) + 1 = 2ⁿ − 1

A solução padrão move a pilha menor duas vezes e o maior disco uma: T(n) = 2T(n − 1) + 1. Um disco exige um movimento; o mínimo para n discos é 2ⁿ − 1.

3 discos: 7 movimentos. 4 discos: 15 movimentos. 5 discos: 31 movimentos.

3 discos — 7 movimentos

Início: todos os discos em A. Destino: C. O disco 1 é o menor.

  1. Mova o disco 1 de A para C.
  2. Mova o disco 2 de A para B.
  3. Mova o disco 1 de C para B.
  4. Mova o disco 3 de A para C.
  5. Mova o disco 1 de B para A.
  6. Mova o disco 2 de B para C.
  7. Mova o disco 1 de A para C.
4 discos — 15 movimentos

Início: todos os discos em A. Destino: C. O disco 1 é o menor.

  1. Mova o disco 1 de A para B.
  2. Mova o disco 2 de A para C.
  3. Mova o disco 1 de B para C.
  4. Mova o disco 3 de A para B.
  5. Mova o disco 1 de C para A.
  6. Mova o disco 2 de C para B.
  7. Mova o disco 1 de A para B.
  8. Mova o disco 4 de A para C.
  9. Mova o disco 1 de B para C.
  10. Mova o disco 2 de B para A.
  11. Mova o disco 1 de C para A.
  12. Mova o disco 3 de B para C.
  13. Mova o disco 1 de A para B.
  14. Mova o disco 2 de A para C.
  15. Mova o disco 1 de B para C.
5 discos — 31 movimentos

Início: todos os discos em A. Destino: C. O disco 1 é o menor.

  1. Mova o disco 1 de A para C.
  2. Mova o disco 2 de A para B.
  3. Mova o disco 1 de C para B.
  4. Mova o disco 3 de A para C.
  5. Mova o disco 1 de B para A.
  6. Mova o disco 2 de B para C.
  7. Mova o disco 1 de A para C.
  8. Mova o disco 4 de A para B.
  9. Mova o disco 1 de C para B.
  10. Mova o disco 2 de C para A.
  11. Mova o disco 1 de B para A.
  12. Mova o disco 3 de C para B.
  13. Mova o disco 1 de A para C.
  14. Mova o disco 2 de A para B.
  15. Mova o disco 1 de C para B.
  16. Mova o disco 5 de A para C.
  17. Mova o disco 1 de B para A.
  18. Mova o disco 2 de B para C.
  19. Mova o disco 1 de A para C.
  20. Mova o disco 3 de B para A.
  21. Mova o disco 1 de C para B.
  22. Mova o disco 2 de C para A.
  23. Mova o disco 1 de B para A.
  24. Mova o disco 4 de B para C.
  25. Mova o disco 1 de A para C.
  26. Mova o disco 2 de A para B.
  27. Mova o disco 1 de C para B.
  28. Mova o disco 3 de A para C.
  29. Mova o disco 1 de B para A.
  30. Mova o disco 2 de B para C.
  31. Mova o disco 1 de A para C.

E se meu tabuleiro for diferente?

Qualquer posição que respeite o tamanho chega a C. Repetir uma posição é um ciclo, não um impasse. A fórmula vale para o início padrão, não para os movimentos restantes de qualquer posição. Peça uma dica para seu tabuleiro atual.

Quebra-cabeças →