1. 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 2^{* *} n-1, 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 2^{n}-1 (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 n>1, faz: mover n-1 discos de origem para auxiliar, mover o disco restante para destino, mover n-1 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 é n=1: mover um único disco da torre de origem para a torre destino é uma operação e conta como um movimento.
  • Para n>1, a solução divide o problema em partes mais simples: mover n-1 discos, fazer um movimento (o disco maior), e mover os n-1 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 T(n) o número de movimentos que a chamada da função faz quando recebe n discos.
  • Para o caso base: T(1)=1porque mover um disco é um movimento.
  • Para n>1, a sequência de ações é:
    1. mover n-1 discos (que são T(n-1) movimentos),
    2. mover 1 disco (o maior) (que são 1 movimento),
    3. mover n-1 discos (outros T(n-1) movimentos).
      Portanto:
    T(n)=T(n-1)+1+T(n-1).
  • 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 n==1: imprime (ou registra) o movimento, e retorna 1.
    • Caso contrário:
      • chama recursivamente para mover n-1 de origem para auxiliar e guarda o número retornado em uma variável, por exemplo mov\_esq.
      • imprime o movimento do disco n de origem para destino e incrementa a contagem em 1.
      • chama recursivamente para mover n-1 de auxiliar para destino e guarda o número retornado em outra variável, por exemplo mov\_dir.
      • retorna mov\_esq + 1 + mov\_dir.
  • Note como essa soma respeita a equação recursiva de T(n) 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 n=3 sem usar fórmula:
  • Para n=1: T(1)=1.
  • Para n=2: pela relação T(2)=T(1)+1+T(1)=1+1+1=3.
  • Para n=3: T(3)=T(2)+1+T(2)=3+1+3=7.
  • Interpretação prática: ao executar a função com n=3, as chamadas recursivas retornarão esses valores e a soma resultará em 7, 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 2^{n}-1; 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)

Exercícios relacionados