1. 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:
  • Precisamos manter a lógica da Torre de Hanói (mover n 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 n discos é:
  1. Mover n-1 discos do pino origem para o pino auxiliar (usando o pino destino).
  2. Mover o disco maior (o de baixo) da origem para o destino — isso é 1 movimento.
  3. Mover os n-1 discos do auxiliar para o destino (usando a origem).
Se chamarmos por exemplo T(n) o número de movimentos para n discos, a recorrência é:
T(n)=2\,T(n-1)+1
com condição base T(0)=0 (ou T(1)=1 se preferir). Vamos ver alguns valores pequenos para internalizar:
T(0)=0,\quad T(1)=1,\quad T(2)=2\cdot1+1=3,\quad T(3)=2\cdot3+1=7.
Essa recorrência tem solução fechada
T(n)=2^{n}-1,
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 1 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 n==0 (ou n==1), não há (ou há apenas um) movimento — retornamos 0 (ou 1).
  • Passo recursivo:
    • chamar recursivamente para mover n-1 discos: isso retorna, digamos, c_1 movimentos.
    • executar (imprimir) o movimento do disco maior: isso é 1 movimento.
    • chamar recursivamente para mover os n-1 discos restantes: isso retorna c_2 movimentos.
    • a função retorna c_1 + 1 + c_2.
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 e mov será igual a 7 (porque 2^{3}-1=7).
  • Exemplo de execução:
    • Primeira chamada: hanoi(3,'A','C','B')
    • Internamente soma retornos das subchamadas e adiciona 1 para o movimento central.
    • Ao final mov = 7. Você pode checar imprimindo print(mov) e verá 7.

Passo 5

Breve comentário sobre eficiência (útil para a prova):
  • O algoritmo faz exatamente T(n)=2^{n}-1 movimentos e tem complexidade temporal O(2^{n}).
  • 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

Exercícios relacionados