- Modifique o código da Torre de Hanói dado na aula síncrona da semana passada de modo que retorne também o número de movimentos realizados, sem utilizar variáveis globais ou a expressão
, ou seja, crie uma solução que envolva a recursão do código para calcular o número de movimentos.
Passo 1
O enunciado pede para modificar o código da Torre de Hanói visto em aula de forma que a função retorne também o número de movimentos realizados. Restrições importantes que o enunciado dá e que devemos respeitar:
- Não usar variáveis globais.
- Não usar a expressão
(ou qualquer fórmula fechada); o número de movimentos deve ser obtido via recursão no próprio código. - A função deve continuar realizando (ou pelo menos descrevendo) os movimentos e, além disso, devolver um inteiro com a contagem total de movimentos.
Informações relevantes do enunciado que usarei:
- O código original já realiza os movimentos recursivamente (presumimos a versão clássica que, para
, faz: mover discos de origem para auxiliar, mover o disco restante para destino, mover discos de auxiliar para destino). - A saída pedida agora é: além dos efeitos colaterais (por ex. imprimir os movimentos), a função deve retornar um número inteiro com a quantidade total de movimentos executados.
Passo 2
Entendimento básico da estrutura que vamos usar (aqui explico sem assumir que você já saiba muito):
- Toda função recursiva precisa de dois elementos claros: o caso base (quando paramos de chamar a função recursivamente) e a chamada recursiva (quando reduzimos o problema).
- No problema da Torre de Hanói o caso base usual é
: mover um único disco da torre de origem para a torre destino é uma operação e conta como um movimento. - Para
, a solução divide o problema em partes mais simples: mover discos, fazer um movimento (o disco maior), e mover os discos restantes. Cada uma dessas partes gera movimentos; somando tudo obtemos o total.
Passo 3
Formulemos a relação que usaremos para contar movimentos através da própria recursão:
- Seja
o número de movimentos que a chamada da função faz quando recebe discos. - Para o caso base:
porque mover um disco é um movimento. - Para
, a sequência de ações é: - mover
discos (que são movimentos), - mover 1 disco (o maior) (que são 1 movimento),
- mover
discos (outros movimentos).
Portanto:
- mover
- Observação pedagógica: essa relação é exatamente a mesma lógica das chamadas recursivas do algoritmo; por isso podemos computar o total somando os valores retornados pelas chamadas recursivas em vez de usar uma fórmula fechada.
Passo 4
Estratégia prática de implementação (passo a passo do raciocínio para traduzir em código):
- Vamos manter a assinatura clássica da função, por exemplo:
def hanoi(n, origem, destino, auxiliar) - Alteração principal: a função vai retornar um inteiro (o número de movimentos realizados pela chamada).
- Implementação lógica:
- Se
: imprime (ou registra) o movimento, e retorna 1. - Caso contrário:
- chama recursivamente para mover
de origem para auxiliar e guarda o número retornado em uma variável, por exemplo . - imprime o movimento do disco
de origem para destino e incrementa a contagem em 1. - chama recursivamente para mover
de auxiliar para destino e guarda o número retornado em outra variável, por exemplo . - retorna
.
- chama recursivamente para mover
- Se
- Note como essa soma respeita a equação recursiva de
mostrada no passo anterior: estamos obtendo o total somando os retornos das chamadas menores mais o movimento do disco atual.
Passo 5
Exemplo numérico manual (para ver que a recursão conta direitinho) — vamos calcular com
sem usar fórmula:
- Para
: . - Para
: pela relação . - Para
: . - Interpretação prática: ao executar a função com
, as chamadas recursivas retornarão esses valores e a soma resultará em , exatamente como queremos — e tudo isso foi calculado usando as próprias chamadas recursivas, sem fórmulas prontas ou variáveis globais.
Passo 6
Dicas para uso na prova e erros comuns para evitar:
- Não use variáveis globais para contar — isso geralmente é proibido e torna difícil raciocinar sobre a recursão.
- Não calcule o total por fora com
; se o enunciado proíbe, a ideia é provar que você entende a recursão e que a função pode produzir o total através das somas dos retornos. - Lembre-se de sempre retornar um inteiro em todas as ramificações (caso base e caso recursivo), para que a soma dos retornos faça sentido.
- Se quiser apenas o número de movimentos sem imprimir, basta remover as linhas que imprimem os movimentos e manter só as somas retornadas.
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 # caso defensivo: nenhum movimento para n<=0
if n == 1:
print(f"Mover disco de {origem} para {destino}")
return 1
# mover n-1 de origem para auxiliar
mov_esq = hanoi(n-1, origem, auxiliar, destino)
# mover o disco n de origem para destino
print(f"Mover disco de {origem} para {destino}")
# mover n-1 de auxiliar para destino
mov_dir = hanoi(n-1, auxiliar, destino, origem)
return mov_esq + 1 + mov_dir
# Exemplo de uso:
# total = hanoi(3, 'A', 'C', 'B')
# print("Total de movimentos:", total)