- Modifique o código da Torre de Hanói dado na aula síncrona de modo que retorne o número de movimentos realizados, sem o uso de variáveis globais. [depois da aula síncrona]
Passo 1
O enunciado pede que a gente modifique o código da Torre de Hanói (o algoritmo recursivo clássico) para que a função retorne o número de movimentos realizados, e sem usar variáveis globais.
Informações relevantes que temos do problema:
Informações relevantes que temos do problema:
- Precisamos manter a lógica da Torre de Hanói (mover
discos de um pino origem para um pino destino usando um pino auxiliar). - A função deve executar (por exemplo, imprimir) os movimentos e, ao final, retornar quantos movimentos foram realizados.
- Não é permitido usar variáveis globais; a contagem de movimentos deve ser obtida por retorno/atribuição local e propagada pela recursão.
Passo 2
Entendendo o algoritmo e a contagem de movimentos (a parte conceitual que você precisa saber para a prova).
A estratégia recursiva para mover discos é:
A estratégia recursiva para mover
- Mover
discos do pino origem para o pino auxiliar (usando o pino destino). - Mover o disco maior (o de baixo) da origem para o destino — isso é 1 movimento.
- Mover os
discos do auxiliar para o destino (usando a origem).
Se chamarmos por exemplo
o número de movimentos para
discos, a recorrência é:
com condição base
(ou
se preferir). Vamos ver alguns valores pequenos para internalizar:
Essa recorrência tem solução fechada
que você pode provar por indução se precisar. Mas para implementar no código não precisamos usar a fórmula explícita: basta que cada chamada recursiva devolva quantos movimentos ela fez, e a chamada pai some essas quantidades e adicione
pelo movimento do disco maior.
Passo 3
Como evitar variáveis globais: cada chamada recursiva deve retornar o número de movimentos que ela realizou. O código do chamador soma os retornos das chamadas filhas e retorna o total. Assim a contagem “sobe” pela pilha de recursão sem usar variáveis externas.
Aqui vai uma explicação linha a linha (em pseudo/Python) e a lógica por trás:
- Caso base: se
(ou ), não há (ou há apenas um) movimento — retornamos (ou ). - Passo recursivo:
- chamar recursivamente para mover
discos: isso retorna, digamos, movimentos. - executar (imprimir) o movimento do disco maior: isso é
movimento. - chamar recursivamente para mover os
discos restantes: isso retorna movimentos. - a função retorna
.
- chamar recursivamente para mover
Exemplo de implementação em Python (comentada para você entender cada parte):
def hanoi(n, origem, destino, auxiliar):
"""
Move n discos de 'origem' para 'destino' usando 'auxiliar'.
Imprime cada movimento e retorna o número total de movimentos realizados.
Não usa variáveis globais.
"""
if n == 0:
# Caso base: nada a mover
return 0
# contador local que acumula movimentos feitos por esta chamada
movimentos = 0
# 1) mover n-1 discos da origem para o auxiliar
movimentos += hanoi(n-1, origem, auxiliar, destino)
# 2) mover o disco maior (agora o único que resta na origem) para o destino
print(f"Mover disco de {origem} para {destino}")
movimentos += 1
# 3) mover os n-1 discos do auxiliar para o destino
movimentos += hanoi(n-1, auxiliar, destino, origem)
# retorna quantos movimentos foram feitos por toda esta operação
return movimentos
Passo 4
Teste prático e interpretação do resultado (como você faria na prova para checar):
- Se você chamar
mov = hanoi(3, 'A', 'C', 'B'), o programa vai imprimir a sequência de movimentos emovserá igual a(porque ). - Exemplo de execução:
- Primeira chamada:
hanoi(3,'A','C','B') - Internamente soma retornos das subchamadas e adiciona
para o movimento central. - Ao final
mov = 7. Você pode checar imprimindoprint(mov)e verá.
- Primeira chamada:
Passo 5
Breve comentário sobre eficiência (útil para a prova):
- O algoritmo faz exatamente
movimentos e tem complexidade temporal . - A implementação acima é simples, clara e evita estado global: toda informação necessária para a contagem é passada/retornada por chamadas.
Resposta
def hanoi(n, origem, destino, auxiliar):
"""
Move n discos de 'origem' para 'destino' usando 'auxiliar'.
Imprime cada movimento e retorna o número total de movimentos realizados.
"""
if n == 0:
return 0
movimentos = 0
movimentos += hanoi(n-1, origem, auxiliar, destino)
print(f"Mover disco de {origem} para {destino}")
movimentos += 1
movimentos += hanoi(n-1, auxiliar, destino, origem)
return movimentos