Algorithme de la Tour de Hanoï : Python, C++ Code
Sarah Chen
⚡ Résumé intelligent
L'algorithme de la tour de Hanoï est un puzzle récursif classique qui déplace une pile de disques entre trois chevilles sans jamais placer un disque plus grand sur un disque plus petit, illustrant clairement le principe « diviser pour régner ».
Qu'est-ce que la Tour de Hanoï ?
La Tour de Hanoï est un casse-tête mathématique composé de trois tiges et d'une pile de disques de tailles décroissantes. Également connue sous le nom de Tour de Brahma ou Tour de Lucas, elle doit son nom au mathématicien français Édouard Lucas qui l'a introduite en 1883. Ce casse-tête s'inspire de légendes concernant le déplacement de disques d'or entre trois tiges.
Ce casse-tête comporte trois tiges et un nombre variable de disques empilés. Les tiges sont disposées en tours cycliques, les plus grands disques étant empilés à la base et les plus petits au sommet.
Au départ, on nous donne trois tiges. L'une d'elles (la tige A dans l'exemple) porte tous les disques empilés. Le but est de déplacer la pile entière d'une tige (A) à une autre (C) en respectant quelques règles précises.
Voici la configuration initiale du puzzle :
Problème de la tour de Hanoï
Et voici l'objectif final :
Règles de la Tour de Hanoï
Voici les règles essentielles de la Tour de Hanoï :
- Dans la configuration initiale du puzzle, tous les disques sont empilés sur la première tige.
- Dans l'état final, tous les disques de la tige une sont empilés sur la tige deux ou la tige trois.
- Un seul disque peut se déplacer d'une tige à l'autre à un instant donné.
- Seul le disque supérieur d'une tige peut être déplacé.
- On ne peut pas placer un disque sur un disque plus petit.
La légende originelle évoquait le déplacement de 64 disques. Les prêtres pouvaient déplacer un disque à la fois, selon des règles précises. D'après la légende, une prophétie annonçait la fin du monde s'ils parvenaient à accomplir cet acte. Dans la section consacrée à la complexité temporelle, nous démontrerons qu'une configuration de type « Tours de Hanoï » avec n disques nécessite 2^n – 1 déplacements.
Donc, si les prêtres avaient besoin de 1 seconde pour déplacer un disque, le temps total pour résoudre le puzzle serait de 2^64 – 1 secondes, soit environ 584 942 417 356 ans, 26 jours, 7 heures et 15 secondes.
Algorithme pour la Tour de Hanoi
La méthode la plus courante pour résoudre le problème des tours de Hanoï est un algorithme récursif. On choisit d'abord deux tiges comme point de départ et d'arrivée ; la tige restante sert de tige auxiliaire.
Voici les étapes pour résoudre le puzzle de la Tour de Hanoï :
- Déplacez les n-1 premiers disques du rattachement source vers le rattachement auxiliaire.
- Déplacez le nième disque de la broche source vers la broche de destination.
- Déplacez les n-1 disques restants de la cheville auxiliaire vers la cheville de destination.
À noter: Si nous n'avons qu'un seul disque, nous pouvons le déplacer directement de la source à la destination.
Comment résoudre le puzzle de la Tour de Hanoi
Illustrons l'algorithme pour trois disques. Considérons la tige A comme la source, la tige B comme l'assistant et la tige C comme la destination.
Étape 1) Au départ, tous les disques sont empilés sur la tige A.
À ce stade : Source = Peg A, Destination = Peg C, Aide = Peg B.
Maintenant, nous devons déplacer les n-1 premiers disques de la source vers l'assistant.
À noter: Bien que nous ne puissions déplacer qu'un disque à la fois, cette étape réduit notre problème à 3 disques à un problème à 2 disques, qui est traité par un appel récursif.
Étape 2) Lorsque nous effectuons un appel récursif depuis le point A avec le point B comme destination, nous utilisons le point C comme auxiliaire.
Remarquez que nous revenons à la première étape du même problème des tours de Hanoï, mais cette fois-ci avec deux disques. Nous déplaçons n-1 (c'est-à-dire un seul) disque de la source vers l'assistant, qui déplace le plus petit disque de la tige A à la tige C.
À ce stade : Source = cheville A, Destination = cheville B, Aide = cheville C.
Étape 3) Selon l'algorithme, le nième (2e) disque est maintenant transféré vers la destination, la cheville B.
À ce stade : Source = cheville A, Destination = cheville B, Aide = cheville C.
Étape 4) Maintenant, nous déplaçons le disque n-1 (disque un) de la cheville auxiliaire C à la cheville de destination B, suivant la troisième étape de l'algorithme.
À ce stade : Source = cheville A, Destination = cheville B, Aide = cheville C.
Étape 5) Une fois l'appel récursif terminé, nous revenons à notre configuration précédente, à la première étape de l'algorithme.
Étape 6) Dans la deuxième étape, nous déplaçons le disque 3 de la broche source A à la broche de destination C.
À ce stade : Source = cheville A, Destination = cheville C, Aide = cheville B.
Étape 7) La prochaine étape consiste à déplacer les disques restants du support (tige B) vers la destination (tige C). Nous utiliserons cette fois la source d'origine (tige A) comme support.
Étape 8) Comme nous ne pouvons pas déplacer deux disques simultanément, nous effectuons un appel récursif pour le disque 1. Conformément à notre algorithme, la destination de cette étape est le piquet A.
À ce stade : Source = cheville B, Destination = cheville A, Aide = cheville C.
Étape 9) L'appel récursif est terminé. Nous déplaçons maintenant le disque 2 de sa source vers sa destination.
À ce stade : Source = cheville B, Destination = cheville C, Aide = cheville A.
Étape 10) Nous terminons en déplaçant le disque n-1 restant (disque 1) de l'assistant vers la destination.
À ce stade : Source = cheville A, Destination = cheville C, Aide = cheville B.
Faux Code pour la tour de Hanoï
START
Procedure Tower_Of_Hanoi(disk, source, dest, helper)
IF disk == 1 THEN
move disk from source to dest
ELSE
Tower_Of_Hanoi(disk - 1, source, helper, dest)
move disk from source to dest
Tower_Of_Hanoi(disk - 1, helper, dest, source)
END IF
END Procedure
Code de programme dans C++
#include <bits/stdc++.h> using namespace std; void tower_of_hanoi(int num, string source, string dest, string helper) { if (num == 1) { cout << " Move disk 1 from tower " << source << " to tower " << dest << endl; return; } tower_of_hanoi(num - 1, source, helper, dest); cout << " Move disk " << num << " from tower " << source << " to tower " << dest << endl; tower_of_hanoi(num - 1, helper, dest, source); } int main() { int num; cin >> num; printf("The sequence of moves :\n"); tower_of_hanoi(num, "I", "III", "II"); return 0; }
Sortie :
3 The sequence of moves : Move disk 1 from tower I to tower III Move disk 2 from tower I to tower II Move disk 1 from tower III to tower II Move disk 3 from tower I to tower III Move disk 1 from tower II to tower I Move disk 2 from tower II to tower III Move disk 1 from tower I to tower III
Code de programme dans Python
def tower_of_hanoi(n, source, destination, helper): if n == 1: print("Move disk 1 from peg", source, "to peg", destination) return tower_of_hanoi(n - 1, source, helper, destination) print("Move disk", n, "from peg", source, "to peg", destination) tower_of_hanoi(n - 1, helper, destination, source) # n = number of disks n = 3 tower_of_hanoi(n, 'A', 'B', 'C')
Sortie :
Move disk 1 from peg A to peg B Move disk 2 from peg A to peg C Move disk 1 from peg B to peg C Move disk 3 from peg A to peg B Move disk 1 from peg C to peg A Move disk 2 from peg C to peg B Move disk 1 from peg A to peg B
Complexité de la Tour de Hanoï
Voici la complexité temporelle et spatiale de la tour de Hanoï :
1) Complexité temporelle :
En revenant à l'algorithme, on constate qu'on effectue un appel récursif pour (n-1) disques, deux fois par appel. Chaque (n-1) récursion se décompose en ((n-1)-1) récursions, et ainsi de suite, jusqu'à atteindre le cas de base à un seul disque.
Pour trois disques :
- Le disque 3 appelle deux fois la fonction récursive du disque 2.
- Le disque 2 appelle deux fois la fonction récursive du disque 1.
- Le disque 1 se déplace en temps constant, ce qui donne le temps nécessaire pour calculer le nombre de disques.
Exprimé sous forme de récurrence :
= 2 × (Temps de calcul pour deux disques) + temps constant pour déplacer le disque 3
= 2 × (2 × temps de résolution pour un disque + temps constant pour déplacer le disque 2) + temps constant pour déplacer le disque 3
= (2 × 2) × temps constant de déplacement du disque 1 + 2 × temps constant de déplacement du disque 2 + temps constant de déplacement du disque 3
Pour n disques, cela devient :
2n-1 × temps constant pour déplacer le disque 1 + 2n-2 × temps constant pour déplacer le disque 2 + ….
Cette progression géométrique a pour somme O(2).n – 1), ce qui se simplifie en O (2n), une complexité temporelle exponentielle.
2) Complexité spatiale :
La complexité spatiale de l'algorithme de la Tour de Hanoï est O(n). La récursivité utilise la pile d'appels, et la profondeur maximale de cette pile est égale à n, le nombre de disques. C'est pourquoi la complexité spatiale est O(n).
