Algorithmes avancés

Tour de Hanoï

Résolution récursive
Le problème des tours de Hanoï est vu en algorithmique (programmation), où il offre un exemple de la puissance et de la lisibilité des programmes définis de façon récursive (un autre exemple étant le tri arborescent). En effet, la méthode de résolution vue précédemment conduit à un algorithme récursif, décrit ci-dessous. Les paramètres de la procédure Déplacer sont :
nombre : nombre de disques utilisés
de : emplacement de départ
à : emplacement de destination
par : emplacement intermédiaire

procédure Déplacer (nombre, de, à, par)
si nombre > 0 alors
Déplacer nombre - 1, de, par, à;
Bouger-un-disque de, à;
Déplacer nombre - 1, par, à, de;
finsi
fin Séplacer

Résolution itérative
Il existe également une procédure itérative pour résoudre le problème des tours de Hanoï. Elle consiste à effectuer successivement les deux déplacements suivants :
• déplacer le plus petit disque d'un emplacement à l'emplacement suivant (de a vers b, de b vers c, de c vers a, par exemple)
• déplacer un autre disque
et à poursuivre itérativement ces deux déplacements jusqu'à ce que la tour complète soit déplacée, le dernier déplacement se limitant alors à celui du plus petit disque sur le sommet de la tour. L'action déplacer un autre disque est non ambigüe puisque, en dehors du plus petit disque, un seul mouvement d'un autre disque est possible.
Contrairement à la procédure récursive, la procédure itérative n'utilise aucune mémorisation de l'arbre des déplacements à effectuer et nécessite seulement de se souvenir si on doit déplacer le plus petit disque ou non, et dans quel sens sont effectués les déplacements du petit disque. Il permet également, à tout moment, de revenir à la situation de départ : il suffit pour cela d'inverser le sens dans lequel se déplace le plus petit disque. Par contre, les raisons pour lesquelles cet algorithme résout le problème sont moins apparentes que pour l'algorithme récursif.
Supposons que la tour soit initialement sur l'emplacement a, et qu'on veuille la déplacer sur l'emplacement b. Nous allons montrer par récurrence sur le nombre N de disques à déplacer que l'itération des deux mouvements décrits précédemment répond à la question, le sens dans lequel est déplacé le plus petit disque étant a → c → b → a → … → b si N est pair, et a → b → c → a → … → b si N est impair. En effet :
• Pour N = 1, il suffit de déplacer l'unique disque de a vers b. Supposons la propriété démontrée pour le déplacement de N-1 disques. Comme dans le cas récursif, on va déplacer la tour de N disques en déplaçant les N-1 disques supérieurs de a vers c, puis le grand disque de a vers b, puis les N-1 disques de c vers b.
• Si N est pair, alors N-1 est impair, et selon l'hypothèse de récurrence (en échangeant les rôles de b et c), lors du déplacement de la pile des N-1 disques supérieurs de a vers c, un déplacement sur deux est effectué par le plus petit disque dans l'ordre a → c → b → a → … → c. On déplace alors le grand disque de a vers b (déplacement qui succède au dernier déplacement du plus petit disque). Puis on déplace les N-1 disques de c vers b, un déplacement sur deux étant effectué par le plus petit disque, cette fois dans l'ordre c → b → a → c → … → b. Finalement, la suite des déplacements du petit disque aura bien été a → c → b → a → … → c → b → a → c → … → b, le plus petit disque étant déplacé une fois sur deux.
• On procédera à une vérification analogue si N est impair.