inthink.guide
LojaVoltar ao início

Joga. Prevê. Compreende.

Torres de Hanói

Joga com 3–5 discos, pede uma pista para a posição atual e aprende a estratégia recursiva com duas animações curtas. Abre um exemplo passo a passo quando precisares.

Jogar às Torres de Hanói
ABCDisco 44Disco 33Disco 22Disco 11

Afasta a pilha pequena para libertar o disco maior.

Regras das Torres de Hanói

  1. Transfere toda a pilha da coluna A para a C.
  2. Move apenas um disco de cada vez, retirando o do topo.
  3. Nunca coloques um disco maior sobre um menor.

Jogar às Torres de Hanói

Escolhe a coluna de origem e depois a de destino. Os números indicam o tamanho: 1 é o menor. Anula uma jogada ou recomeça para tentar outra abordagem.

0 jogada
ABCDisco 33Disco 22Disco 11

Escolhe a origem e depois o destino.

As pistas partem da tua posição e não movem discos por ti. Um desvio permitido continua a ter solução.

Como resolver as Torres de Hanói

Pensa primeiro no disco maior. Neste exemplo de quatro discos, três pequenos bloqueiam-no. Resolve esse problema menor antes de mover o disco 4.

  1. Afasta a pilha pequena

    Move os discos 1, 2 e 3 de A para B, usando C como auxiliar. Mantém o disco 4 em A. C fica livre e o disco 4 acessível.

    ABCDisco 44Disco 33Disco 22Disco 11

  2. Move o disco maior

    Move o disco 4 de A para C. Esta jogada coloca-o na posição final.

    ABCDisco 44Disco 33Disco 22Disco 11

  3. Leva a pilha pequena ao destino

    Move os discos 1, 2 e 3 de B para C, usando A como auxiliar. Cabem sobre o disco 4 e o problema fica resolvido.

    ABCDisco 44Disco 33Disco 22Disco 11

Cada pilha menor repete o plano: afastar os discos acima do maior, movê-lo e voltar a colocar a pilha pequena por cima. Com um só disco, move-o diretamente. Isto é recursão; origem, destino e coluna auxiliar mudam em cada subproblema.

Aprende prevendo o próximo objetivo

Estes exemplos separados com quatro discos não alteram o teu jogo. Faz uma pausa, avança uma jogada, responde a uma previsão ou mostra a explicação.

1. Liberta o disco maior

Vê três discos pequenos abrir espaço para o disco 4. Prevê onde devem estar antes de mover o maior.

Exemplo separado com quatro discos

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

ABCDisco 44Disco 33Disco 22Disco 11

Abre primeiro o caminho: move os três discos de cima de A para B.

Passo 0 de 8

2. Repete o problema menor

O disco 4 já está em C. Resta o mesmo problema com três discos e novos papéis para as colunas.

Exemplo separado com quatro discos

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

ABCDisco 44Disco 33Disco 22Disco 11

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

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

Passo 0 de 7

Soluções passo a passo

Os exemplos começam com todos os discos em A e terminam em C. Abre-os diretamente; o teu jogo mantém-se.

Número mínimo de jogadas

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

A solução padrão move a pilha pequena duas vezes e o maior disco uma: T(n) = 2T(n − 1) + 1. Um disco precisa de uma jogada, logo o mínimo para n discos é 2ⁿ − 1.

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

3 discos — 7 jogadas

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

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

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

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

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

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

E se a minha posição for diferente?

Qualquer posição que respeite os tamanhos pode chegar a C. Repetir uma posição é um ciclo, não um beco sem saída. A fórmula aplica-se ao início padrão, não às jogadas restantes numa posição qualquer. Pede uma pista para o teu tabuleiro.

Quebra-cabeças →