Tours de Hanoï

Un article de Freepedia.

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 2^N - 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 <math>x_N</math> 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 :

<math>
\left\{\begin{matrix}
x_1=1, \\
x_N = 2x_{N-1} + 1, & \mbox{si }N>1
\end{matrix}\right.
</math>
<math>
\mbox{ce qui donne bien } 
x_N=2^N-1\,</math>

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

exemple de l'application de l'algorithme de resolution recursif en langage C :

 my_putchar(char c)
 {
     write (1, &c, 1); //on ecrit le caractere
 }
 int     my_hanoi_rec(char pic_depart, char pic_dest, char pic_trans, int nb_disques)
 {
   if (nb_disques == 1)
     {
       my_putchar(pic_depart); //on envois les caracteres a imprimer
       my_putchar('-');
       my_putchar('>');
       my_putchar(pic_dest);
       my_putchar('\n');
     }
   else
     {
       my_hanoi_rec(pic_depart, pic_trans, pic_dest, nb_disques - 1); //on modifie les positions des palets 
       my_hanoi_rec(pic_depart, pic_dest, pic_trans, 1);
       my_hanoi_rec(pic_trans, pic_dest, pic_depart, nb_disques - 1);
     }
 }
 int     my_hanoi(int nb_disques)
 {
   my_hanoi_rec('1', '2', '3', nb_disques);
   return(0);
 }

Liens externes

• Site de jeux
• Tours de Hanoï avec résolution