Tours de Hanoï
Tower_of_Hanoi.gif
Le problème des tours de Hanoï est un jeu de réflexion imaginé par le mathématicien Édouard Lucas, et consistant à déplacer des disques de diamètres différents d'une tour de « départ » à une tour d'« arrivée » en passant par une tour « intermédiaire » et ceci en un minimum de coups, tout en respectant la règle suivante : on ne peut placer sur un disque un autre disque plus grand que lui. On suppose que cette règle est également respectée dans la configuration de départ.
Il est facile de démontrer par récurrence que si N est le nombre de disques, il faut 2N - 1 coups au minimum pour parvenir à ses fins, ce qui augmente très rapidement le temps nécessaire pour résoudre ce problème. En effet, soient a, b et c les trois emplacements des tours. Notons xN le nombre de déplacements de disques nécessaires au déplacement d'une tour complète. Pour déplacer une tour de N disques a vers b, on déplace la tour des N-1 premiers disques de a vers c, puis le disque N de a vers b, puis la tour des N-1 disques de c vers b. Le nombre de déplacements de disques vérifie donc la relation de récurrence :
- xN = 2xN − 1 + 1 avec x1 = 1
ce qui donne bien xN = 2N − 1
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 é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 :
sub 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;
fin-du-si
fin-du-sub