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 hanoi(1,,ori>=m,destino,auxiliar) ;=; imprimir Mova 1 disco de ori>=m para destino , 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:

Passo 3

Caso recursivo (a mágica acontece):
Para mover hanoi(n,;o,;d,;a);=; hanoi(n-1,,o,,a,,d) imprimir Mova disco de o para d hanoi(n-1,,a,,d,,o) discos de uma haste “origem” para “destino”, usando “auxiliar”, a gente faz três passos:
  1. Move recursivamente os discos do topo de origem para auxiliar.
  2. Move o disco maior (o -ésimo) de origem para destino.
  3. 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:
function hanoi(n,o,d,a): if n=1 then print("Mova disco de " + o + " para " + d) else hanoi(n-1,,o,,a,,d) print("Mova disco de " + o + " para " + d) hanoi(n-1,,a,,d,,o) end if

Passo 5

Pra ver na prática, chama a função com hanoi(3,,A,,C,,B) , origem=A, destino=C e auxiliar=B:
Isso vai imprimir a sequência de 7 movimentos:
  1. Mova disco de A para C
  2. Mova disco de A para B
  3. Mova disco de C para B
  4. Mova disco de A para C
  5. Mova disco de B para A
  6. Mova disco de B para C
  7. Mova disco de A para C

Resposta

Função recursiva em LaTeX-pseudocódigo:
function hanoi(n,o,d,a): if n=1 then print("Mova disco de " + o + " para " + d) else hanoi(n-1,,o,,a,,d) print("Mova disco de " + o + " para " + d) hanoi(n-1,,a,,d,,o) end if
E, para , a sequência de movimentos é:
  1. A → C
  2. A → B
  3. C → B
  4. A → C
  5. B → A
  6. B → C
  7. A → C

Exercícios relacionados