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