Tours de Hanoï
Dans cet exercice, vous allez implémenter l'énigme des Tours de Hanoï avec un algorithme récursif. Le but du jeu est de transférer tous les disques d'une des trois tiges vers une autre, en respectant ces règles :
- Vous ne pouvez déplacer qu'un seul disque à la fois.
- Vous ne pouvez prendre que le disque du dessus d'une pile et le déposer sur le dessus d'une autre pile.
- Vous ne pouvez pas placer un disque plus grand sur un plus petit.
L'algorithme présenté est une implémentation de ce jeu avec quatre disques et trois tiges nommées « A », « B » et « C ». Le code contient deux erreurs. En fait, si vous l'exécutez, il fait planter la console parce qu'il dépasse la profondeur de récursion maximale. Pouvez-vous trouver les bogues et les corriger ?
Cette activité fait partie du cours
Structures de données et algorithmes en Python
Instructions de l’exercice
- Corrigez le cas de base.
- Corrigez les appels à la fonction
hanoi().
Exercice interactif pratique
Essayez cet exercice en complétant ce code d’exemple.
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)