Torres de Hanoi. Implemente a função hanoi(num), onde num é a quantidade de blocos do problema da torre de hanoi. A sua função deve dizer qual o movimento realizado e quantos blocos tem em cada torre após cada movimento.

Passo 1

Então, o exercício é sobre as Torres de Hanoi. A ideia aqui é criar uma função chamada hanoi(num) onde num representa a quantidade de blocos que temos. O conteúdo principal envolve recursão, que é quando uma função chama a si mesma para resolver subproblemas menores. Vamos precisar entender como mover os blocos entre três torres seguindo as regras das Torres de Hanoi.

Passo 2

Primeiro, vamos entender as regras básicas das Torres de Hanoi:
  1. Só podemos mover um bloco por vez.
  2. Um bloco maior nunca pode ficar em cima de um bloco menor.
  3. Temos três torres: origem, destino e auxiliar.

Passo 3

A estratégia para resolver o problema com num blocos é:
  • Mover os num - 1 blocos superiores da torre de origem para a torre auxiliar.
  • Mover o bloco maior restante da torre de origem para a torre de destino.
  • Mover os num - 1 blocos da torre auxiliar para a torre de destino.

Passo 4

Vamos implementar isso usando recursão. A função hanoi vai precisar de parâmetros adicionais para rastrear as torres envolvidas em cada movimento. Vamos definir as torres como origem, destino e auxiliar.

Passo 5

Além disso, vamos manter o controle dos blocos em cada torre após cada movimento. Podemos usar dicionários para representar as torres e suas pilhas de blocos.

Passo 6

Agora, vamos escrever o código passo a passo:
def hanoi(num, origem='A', destino='C', auxiliar='B', torres=None, movimentos=[]):
    if torres is None:
        torres = {origem: list(range(num, 0, -1)), destino: [], auxiliar: []}
    
    if num == 1:
        bloco = torres[origem].pop()
        torres[destino].append(bloco)
        movimentos.append(f"Mover bloco {bloco} de {origem} para {destino}")
        print(f"{movimentos[-1]}\nTorres: {torres}")
    else:
        hanoi(num-1, origem, auxiliar, destino, torres, movimentos)
        hanoi(1, origem, destino, auxiliar, torres, movimentos)
        hanoi(num-1, auxiliar, destino, origem, torres, movimentos)
    
    return movimentos, torres

Resposta

Para testar a função com, por exemplo, 2 blocos:

movimentos, torres = hanoi(2)
for movimento in movimentos:
print(movimento)
print(“Estado final das torres:”, torres)

# Explicação Final
Esse código implementa a solução das Torres de Hanoi. Ele move os blocos de forma recursiva, registrando cada movimento e mostrando o estado das torres após cada passo. Ao final, você verá todos os movimentos necessários para resolver o problema e o estado final das torres.

Exercícios relacionados