Le problème dit des “Tours de Hanoi” peut être vu comme un exercice récréatif, un casse-tête, un jeu mathématique, … Il fait l’objet d’une abondante littérature sur Internet, présentant à la fois la légende d’où il serait issu, de nombreuses animations illustrant sa résolution, des variantes et de savants développements mathématiques … Sa résolution est une très simple et intéressante application récursive de parcours infixé d’arbre !
- Le problème
Le jeu est constitué de 3 pieux (ou pivots), et de N anneaux de diamètres strictement décroissants enfilés initialement sur l’un des pieux et constituant une “tour”. Il s’agit de faire passer les N anneaux du pieu initial sur l’un des deux autres pieux, en respectant les règles suivantes :
- les anneaux ne peuvent être déplacés qu’un seul à la fois,
- seul l’anneau du dessus d’une tour peut être déplacé,
- un anneau peut être prélevé de n’importe quelle tour et enfilé sur n’importe quel autre pieu à condition qu’il ne soit jamais posé sur un anneau de diamètre inférieur.
Le jeu consiste à effectuer le moins de déplacements possible !
Ecrire la procédure récursive Hanoi() qui décrit les mouvements élémentaires des disques. Elle reçoit en paramètres-données :
- le nombre d’anneaux de la tour à déplacer,
- les identifiants (un simple caractère) des pieux respectivement initial, final et intermédiaire.
Construire l’arbre des appels.