Torres de Hanói
Neste exercício, você implementará o quebra-cabeça Towers of Hanoi com um algoritmo recursivo. O objetivo deste jogo é transferir todos os discos de uma das três hastes para outra, seguindo estas regras:
- Você só pode mover um disco de cada vez.
- Você só pode pegar o disco superior de uma das pilhas e colocá-lo no topo de outra pilha.
- Você não pode colocar um disco maior em cima de um menor.
O algoritmo mostrado é uma implementação desse jogo com quatro discos e três hastes chamadas 'A', 'B' e 'C'. O código contém dois erros. Na verdade, se você executá-lo, ele trava o console porque excede a profundidade máxima de recursão. Você consegue encontrar os erros e corrigi-los?
Este exercício faz parte do curso
Estruturas de dados e algoritmos em Python
Instruções de exercício
- Corrija o caso base.
- Corrija as chamadas para a função
hanoi().
Exercício interativo prático
Experimente este exercício preenchendo este código de exemplo.
def hanoi(num_disks, from_rod, to_rod, aux_rod):
# Correct the base case
if num_disks >= 0:
# Correct the calls to the hanoi function
hanoi(num_disks, from_rod, aux_rod, to_rod)
print("Moving disk", num_disks, "from rod", from_rod,"to rod",to_rod)
hanoi(num_disks, aux_rod, to_rod, from_rod)
num_disks = 4
source_rod = 'A'
auxiliar_rod = 'B'
target_rod = 'C'
hanoi(num_disks, source_rod, target_rod, auxiliar_rod)