Torre de Hanói: considerando 3 torres, o objetivo é transferir 3 discos que estão na torre A para a torre C, usando uma torre B como auxiliar. Somente o último disco de cima de uma pilha pode ser deslocado para outra, e um disco maior nunca pode ser colocado sobre um menor. Implementar uma função recursiva que mostra a seqüência de movimentos para resolver o problema da Torre de Hanói.
Passo 1
Beleza, então o problema é a Torre de Hanói com 3 discos: a gente precisa passar todos da haste A pra C, usando a haste B como apoio. Isso é um clássico de recursão: a ideia-chave é que pra mover
discos você reutiliza a mesma estratégia pra
. Vamos precisar entender bem o caso-base (quando não dá pra recursão) e o caso recursivo (quando você chama a si mesmo pra resolver subproblemas menores).
Passo 2
Caso-base (a teoria aqui é que recursão precisa de um ponto em que ela pare):
Se , não tem mistério: você simplesmente pega o disco de cima da haste de origem e coloca na haste de destino. Em pseudocódigo matemático:
Se
Passo 3
Caso recursivo (a mágica acontece):
Para mover discos de uma haste “origem” para “destino”, usando “auxiliar”, a gente faz três passos:
Para mover
- Move recursivamente os
discos do topo de origem para auxiliar. - Move o disco maior (o
-ésimo) de origem para destino. - Move recursivamente os
discos que estão em auxiliar para destino.
Em fórmulas LaTeX:
Passo 4
Agora, juntando tudo, a função recursiva fica assim em LaTeX-pseudocódigo:
Passo 5
Pra ver na prática, chama a função com
, origem=A, destino=C e auxiliar=B:
Isso vai imprimir a sequência de 7 movimentos:
- Mova disco de A para C
- Mova disco de A para B
- Mova disco de C para B
- Mova disco de A para C
- Mova disco de B para A
- Mova disco de B para C
- Mova disco de A para C
Resposta
Função recursiva em LaTeX-pseudocódigo:
E, para
, a sequência de movimentos é:
- A → C
- A → B
- C → B
- A → C
- B → A
- B → C
- A → C