Ir para o conteúdo principal

Como Dominar a Torre de Hanói

TLDR: A Torre de Hanói é resolvida por uma regra recursiva: para mover n discos para o pino de destino, primeiro mova n-1 discos para o pino do meio, depois mova o maior disco para o destino, depois mova n-1 discos por cima. Aplique esta regra em todos os níveis e você sempre atingirá o número mínimo de movimentos. O mínimo é sempre um a menos que uma potência de dois: 3 discos precisa de 7 movimentos, 4 discos precisa de 15, 5 precisa de 31, 6 precisa de 63, 7 precisa de 127.

O Que é o Jogo

A Torre de Hanói começa com uma pilha de discos no pino mais à esquerda, o maior na parte inferior, o menor no topo. Seu objetivo: mover toda a pilha para o pino mais à direita, obedecendo a duas regras. Mova um disco de cada vez. Nunca coloque um disco maior em cima de um menor.

É isso. Sem temporizadores, sem aleatoriedade, sem informação oculta. Apenas lógica e um orçamento de movimentos.

O PlayMemorize vai de 3 a 7 discos. O orçamento de movimentos começa acima do mínimo ótimo para que iniciantes ainda possam vencer enquanto aprendem o padrão; à medida que seu nível sobe, o orçamento se aperta em direção ao mínimo matemático.

As contagens mínimas de movimentos: 3 discos = 7 movimentos, 4 discos = 15 movimentos, 5 discos = 31 movimentos, 6 discos = 63 movimentos, 7 discos = 127 movimentos. Cada nível requer aproximadamente o dobro dos movimentos do nível abaixo, mais um. Se você exceder o orçamento de movimentos, a rodada termina como derrota.

Tower of HanoiOpen game
Loading...

O Algoritmo Recursivo

Tudo na Torre de Hanói segue um padrão, aplicado repetidamente em cada escala:

Para mover n discos do pino A para o pino C, usando o pino B como armazenamento temporário:

  1. Mova n-1 discos de A para B (usando C como temporário)
  2. Mova o maior disco de A para C
  3. Mova n-1 discos de B para C (usando A como temporário)

Esse é o algoritmo completo. Em cada nível do quebra-cabeça, você está executando essa mesma estrutura de três etapas. A beleza é que as etapas 1 e 3 são elas próprias instâncias menores do mesmo problema, resolvidas pela mesma regra.

Vamos rastrear 3 discos para concretizar. Meta: mover os três do pino 1 para o pino 3. - Etapa 1 (mover 2 discos do pino 1 para o pino 2): mova o disco 1 para o pino 3, mova o disco 2 para o pino 2, mova o disco 1 para o pino 2. - Etapa 2 (mover o disco 3 do pino 1 para o pino 3): um movimento. - Etapa 3 (mover 2 discos do pino 2 para o pino 3): mova o disco 1 para o pino 1, mova o disco 2 para o pino 3, mova o disco 1 para o pino 3.

Total: 7 movimentos. Ótimo.

Pensamento em Três Fases. Antes de tocar em qualquer disco, nomeie as três fases em voz alta: “Limpe n-1 discos para o meio; mova o maior para o destino; reconstrua n-1 discos por cima.” Em cada nível de recursão, você está repetindo essa mesma estrutura com um disco a menos. Você não está memorizando uma sequência de movimentos - você está executando um padrão fractal.

Dica: Antes de fazer qualquer movimento, pergunte: “Qual é o maior disco que preciso mover agora?” Tudo que você faz até mover esse disco é preparação. Manter esse enquadramento evita movimentos sem propósito e o mantém no caminho ótimo.

Por Que a Contagem de Movimentos é Fixa

A contagem mínima de movimentos segue diretamente do algoritmo. Resolver n discos requer resolver n-1 discos duas vezes (etapas 1 e 3) mais um movimento do maior disco (etapa 2). Então o total T(n) = 2 vezes T(n-1) mais 1. Com T(1) = 1, isso se expande para: 1, 3, 7, 15, 31, 63, 127 para contagens de discos de 1 a 7.

Cada número é um a menos que uma potência de dois. Três discos: 8 menos 1 = 7. Quatro discos: 16 menos 1 = 15. Cinco discos: 32 menos 1 = 31. Seis discos: 64 menos 1 = 63. Sete discos: 128 menos 1 = 127.

Isso não é coincidência - é a consequência direta de resolver n-1 discos duas vezes cada vez que você resolve n discos. Uma vez que você entende isso, para de ver Hanói como um quebra-cabeça para adivinhar e começa a vê-lo como um algoritmo a executar.

Táticas por Dificuldade

3 a 4 discos (aprendizado): Neste nível, o orçamento de movimentos é confortável. Foque em nomear cada disco mentalmente - “pequeno”, “médio”, “grande” - para nunca confundir qual disco você está mirando. Rastreie as três fases antes de tocar em qualquer coisa. Após cada jogo, explique as fases em voz alta: “Limpei dois discos para o meio, movi o grande, reconstruí por cima.”

Dica: O maior disco deve se mover exatamente uma vez por solução completa. Se você se encontrar querendo movê-lo novamente, a estrutura do algoritmo quebrou. Retorne ao enquadramento de três fases e identifique onde você saiu dos trilhos.

5 a 6 discos (intermediário): O orçamento de movimentos aperta. Cada movimento errante custa. Aplique o algoritmo recursivo estritamente em cada nível. Quando você recursa de n para n-1 discos, seu foco mental deve mudar: você agora está resolvendo um quebra-cabeça de Hanói menor com um conjunto diferente de pinos “origem”, “destino” e “auxiliar”. Rastreie qual papel cada pino desempenha em cada nível de recursão.

A Troca do Pino Auxiliar. Em cada nível de recursão, um pino é a origem, um é o destino e um é auxiliar. Esses papéis giram à medida que você recursa. Ao mover n-1 discos do pino 1 para o pino 2, o pino 3 é auxiliar. Ao então mover n-2 discos do pino 1 para o pino 3, o pino 2 é auxiliar. Rastreie essa troca conscientemente - é a fonte mais comum de confusão em 5 e 6 discos.

7 discos (desafio): Com 127 movimentos mínimos e um orçamento apertado, você não pode pensar movimento por movimento. Pense fase por fase. Antes de começar, mapeie a estrutura de nível superior: mova 6 discos para o meio (63 movimentos), mova o maior disco para a direita (1 movimento), mova 6 discos para a direita (63 movimentos). Depois subdivida cada fase de 6 discos da mesma forma. Esse planejamento de cima para baixo reduz a carga cognitiva e evita o erro de perder o controle de qual fase você está.

Cuidado: Com 7 discos, tentar memorizar a sequência movimento por movimento é não confiável e desnecessário. Confie no algoritmo. Quando você aplica a regra recursiva em cada ponto de ramificação, o movimento correto é sempre determinado. A dúvida e a segunda adivinhação são como você queima movimentos e esgota o orçamento.

Tower of HanoiOpen game
Loading...

Erros Comuns

Tratá-lo como um quebra-cabeça de tentativa e erro. Movimentos aleatórios ocasionalmente parecem produtivos mas se acumulam em becos sem saída. Hanói é um algoritmo, não um quebra-cabeça para resolver por experimentação. Remova a aleatoriedade do seu pensamento completamente.

Perder o controle dos papéis dos pinos. Em três pinos idênticos, “origem”, “destino” e “auxiliar” podem se confundir, especialmente em contagens de discos mais altas. Antes de começar, rotule os pinos explicitamente em sua mente: ESQUERDA = início, CENTRO = meio, DIREITA = destino. Use esses rótulos consistentemente em todo nível de recursão.

Mover o maior disco mais de uma vez. No nível superior de recursão, o maior disco se move exatamente uma vez. Se sentir vontade de movê-lo novamente, pare - a estrutura do algoritmo quebrou. Retorne ao enquadramento de três fases e identifique onde você saiu dos trilhos.

O Ponto de Verificação do Maior Disco. Em cada nível de recursão, o n-ésimo disco deve se mover exatamente uma vez. Após completar a primeira subfase (mover n-1 discos para o pino auxiliar), o n-ésimo disco deve estar livre e sem ter sido movido. Após a etapa 2, deve estar no pino de destino. Se não estiver, você desviou do algoritmo.

Ficar sem movimentos. Isso só acontece quando você não está seguindo o algoritmo, ou quando você fez e depois mentalmente “desfez” movimentos (mudou de ideia no meio da execução e tentou um caminho diferente). Comprometa-se com o algoritmo. Ele é ótimo - não há caminho melhor.

Cuidado: Uma vez que você decidiu sobre um movimento usando o algoritmo recursivo, comprometa-se. Questionar isso durante a execução leva a movimentos desperdiçados. O algoritmo garante otimidade - confie nele e execute sem hesitação.

Um Plano de Prática

Semana 1 - Internalização do algoritmo (3 discos). Jogue jogos de 3 discos diariamente. Após cada jogo, descreva as três fases em voz alta. Repita até que o padrão seja tão familiar que você possa narrar toda a solução antes de fazer o primeiro movimento.

Semana 2 - Escalando (4 a 5 discos). Passe para jogos de 4 discos. A recursão agora vai dois níveis de profundidade. Após cada jogo, rastreie a estrutura: “Recursei para 3, movi o disco grande, recursei novamente.” Jogue três a quatro jogos com 4 discos, depois passe para 5.

Semana 3 - Pressão (6 discos). Com 6 discos, o orçamento de movimentos torna-se a restrição vinculante. Jogue com o algoritmo como único guia. Mire em completar dois jogos de 6 discos dentro de cinco movimentos do mínimo (63 movimentos). Rastreie sua contagem de movimentos e veja-a cair em direção a 63 ao longo da semana.

Semana 4 - Domínio (7 discos). Tente quebra-cabeças de 7 discos. Aplique o planejamento de fases de cima para baixo antes de tocar em qualquer disco. Três vitórias consecutivas com 7 discos com uma contagem de movimentos próxima de 127 sinaliza domínio genuíno.

Dica: Mantenha um registro de suas contagens de movimentos por nível de discos. Assistir sua contagem cair em direção ao mínimo ao longo das sessões é o sinal externo mais claro de que o padrão recursivo está internalizando. Contagens acima de 130 para 7 discos significa que movimentos errantes ainda estão aparecendo; abaixo de 135 com consistência significa que a estrutura está sólida.

A Torre de Hanói é um dos poucos jogos onde o domínio é absoluto e mensurável. Ou você conhece o algoritmo recursivo e o executa, ou não. Uma vez que você o faz, cada nível de dificuldade cede à mesma lógica. Desacelere, nomeie suas fases, confie no algoritmo e a solução está sempre lá.

Novos vídeos de jogos no YouTube

Novos vídeos de jogos no YouTube Fazemos um vídeo curto de cada jogo. Subscreve para ver os novos.

OK

Grátis na web Quer jogar offline e apoiar o PlayMemorize? Experimente o app.

Baixar app