Tours de Hanoï
Dans cet exercice, vous allez implémenter l'énigme des Tours de Hanoï avec un algorithme récursif. Le but est de déplacer 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 supérieur d'une pile et le poser au sommet d'une autre pile.
- Vous ne pouvez pas poser 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 l'état, si vous l'exécutez, il fait planter la console car il dépasse la profondeur maximale de récursion. Saurez-vous trouver les bugs et les corriger ?
Cet exercice fait partie du cours
<cours>Structures de données et algorithmes en Python</cours>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)