Les Tours de Hanoï

 

I Présentation

I.1 Règle

Le jeu des tours de Hanoï consiste en une plaquette de bois sur laquelle sont plantées 3 tiges. Sur ces tiges sont enfilés des disques de bois dont les diamètres sont tous différents. La seule règle du jeu est de ne jamais poser un disque sur un disque plus petit que lui. Au début du jeu tous les disques sont posés sur la tige de gauche. Le but du jeu est de déplacer tous les disques (qui sont donc au départ tous enfilés sur la tige de gauche), vers la tige de droite, sans jamais violer la règle.

            Situation de départ :                                   
                                                                    
                       |               |               |            
                       |               |               |            
                    ---+---            |               |            
                       |               |               |            
                  -----+-----          |               |            
                ================================================     
                                                                    


            Situation d'arrivée :                                   
                                                                    
                       |               |               |            
                       |               |               |            
                       |               |            ---+---         
                       |               |               |            
                       |               |          -----+-----       
                ================================================    
                                                                    
              ( sachant qu'il y a évidemment plus de 2 disques).

 

I.2 La légende

Le jeu original était accompagné d'une notice racontant la légende de moines d'un temple de Hanoï qui passaient leur temps à résoudre ce jeu pour atteindre le nirvana. En effet, les moines croyaient que la fin du monde arriverait lorsque le jeu serait achevé. Leur jeu grandeur nature occupait la cour d'un temple. Il se composait de 64 disques d'or et de 3 tiges d'ivoire d'un mètre de haut.

Nous allons voir que ce jeu, sous ses allures simples, peut demander pas mal de temps avant d'être résolu. C'est un vrai casse-tête. Mais, alors qu'un être humain mettra du temps à arriver au bout de ce jeu, l'ordinateur va trouver en quelques minutes la solution, simplement en utilisant une règle, bien pratique en informatique et en mathématique : la récursivité.

 

I.3 Le programme fourni

Mais avant de commencer à étudier le problème, je vous conseille de mettre la main à la pâte en essayant manuellement de résoudre le problème : démarrez le programme puis choisissez l'option Manuellement. Passez y quelques minutes... avant d'abandonner (si, si, vous abandonnerez. Je ne dis pas que vous ne réussirez pas à trouver mais simplement que vous en aurez vite marre, surtout si vous y allez à tâtons).

Maintenant que vous avez essayé, choisissez l'option {automatiqueðAUTOHANOI} pour voir l'ordinateur se débrouiller comme un Dieu, et vous éclater purement et simplement.

Ca dégoûte, hein !!

 

II Le programme

II.1 Le principe de la récursivité

Il faut dire que ce jeu est une parfaite démonstration de l'utilité de la récursivité. La règle du jeu est simple (ne pas déposer un disque sur un disque plus petit), la solution l'est aussi.

La récursivité consiste à dire : "je suppose que je sais comment faire pour les n-1 premiers cas, comment faire pour le nième cas ?". Appliquons cela à nos tours.

 

II.2 L'algorithme

Supposons que les tiges s'appellent A, B, et C, que n soit le nombre de disques, tous posés au départ sur la tige A, et que nous devions les mettre sur la tige C. Appliquons le principe de la récursivité : "je suppose que je sais comment faire pour déplacer les n-1 premiers disques de la tige A vers la tige B, sans violer la règle, comment faire pour déplacer le nième (qui est sur la tige A) vers la tige C, toujours sans violer la règle ?".

Et là, l'illumination vous atteint : Eurêka ! J'ai trouvé ! Eh oui, il suffit simplement de déplacer le dernier disque (donc le plus gros) de la tige A vers la tige C (qui est vide, donc pas de violation de la règle), puis de déplacer les n-1 disques qui sont sur la tige B vers la tige C, par au-dessus, et cela sans violer la règle puisque c'est le plus gros qui se trouve maintenant sur la tige C. Oui, d'accord, mais comment faire pour déplacer les n-1 disques de la tige B vers la tige C ? Eh bien puisque vous avez réussi à les déplacer de la tige A vers la tige B (c'est la supposition que vous avez faite pour le principe de la récursivité, voir plus haut), vous serez capable de les déplacer de la tige B vers la tige C.

Voilà donc le problème résolu pour n disques, en partant du principe que vous savez le résoudre pour n-1 disques.

Mais nous savons aussi résoudre le problème pour 0 disques : il n'y a rien à faire. Nous savons donc résoudre le problème des tours de Hanoï pour tout n.

Voici donc la décomposition à faire, lorsque l'on a n disques :

  1. Je transfère les n-1 disques de la tige A vers la tige B
  2. Puis je déplace le nième disque de la tige A vers la tige C
  3. Je transfère les n-1 disques de la tige B vers la tige C
Aide : pour mieux saisir la récursivité, il faut toujours réfléchir en ignorant totalement comment on fait pour les états précédents. Ca peut paraître paradoxal puisqu'on suppose connus ces états mais c'est ainsi, et ma foi, c'est bien pratique. Ainsi, ici, j'ignore totalement comment il faut faire pour les n-1 disques mais par contre, je sais très bien ce qu'il faut faire pour déplacer le dernier.

On obtient donc l'algorithme suivant:


    Procédure Hanoï(tige1, tige2, tige3 : caractère; nbdisques : entier) 
                                                                         
    Début                                                                
                                                                         
      Si (nbdisques>0)                                                   
                                                                         
        Alors Début                                                      
                                                                         
            Hanoï(tige1,tige3,tige2,nbdisques-1)                         
                                                                         
            Déplace(tige1,tige3)                                         
                                                                         
            Hanoï(tige2,tige1,tige3,nbdisques-1)                         
                                                                         
        Fin                                                              
                                                                         
    Fin                                                                  
avec Déplace(de,vers : caractère) une procédure qui déplace le disque posé sur la tige "de" vers la tige "vers".

 

III Complexité

III.1 Complexité du programme

Déterminons maintenant le nombre de déplacements effectués (le nombre d'appels à la procédure Déplace) lorsqu'on joue avec n disques. Appelons coût(n) ce nombre.

coût(n) est donc le nombre de déplacements effectués lorsqu'on appelle la procédure Hanoï avec n comme argument (Hanoï(x,y,z,n)).

Pénétrons maintenant dans le corps de la procédure :


   Si(nbdisques>0)                                                         
                                                                           
   /* c'est bon puisque n>0)                                            */ 
                                                                           
   Alors Début                                                             
                                                                           
     Hanoï(tige1,tige3,tige2,nbdisques-1)                                  
                                                                           
   /* à  la  suite  de cet appel, il y aura d'autres appels à "déplace" */ 
   /* mais  combien  ?  Simple,  il  y  en  aura  coût(n-1) car on joue */ 
   /* désormais avec n-1 disques                                        */ 
                                                                           
     Déplace(tige1,tige3)                                                  
                                                                           
   /* Là c'est clair, il y a 1 déplacement                              */ 
                                                                           
     Hanoï(tige2,tige1,tige3,nbdisques-1)                                  
                                                                           
   /* Là  pareil,  on  joue  désormais avec n-1 disques, d'où coût(n-1) */ 
   /* déplacements                                                      */ 

Ce qui donne pour la procédure de Hanoï:

    coût(n) = coût(n-1)+1+coût(n-1)
            = 2*coût(n-1)+1
	    

Et pour 0 disques, c'est simple, il n'y a aucun déplacement à faire, d'où :

     coût(n) = 2*coût(n-1)+1                                               
     coût(0) = 0                                                           

Bien, mais ça ne nous donne toujours pas le nombre de déplacements effectués.
Voyons voir pour n-1, n-2,...

    coût(n-1) = 2*coût(n-2)+1                                             
    coût(n-2) = 2*coût(n-3)+1                                             
    ...                                                                   
    coût(0)   = 0                                                         

Ca donne :

    coût(n) = 2*(2*coût(n-2)+1)+1                                         
            = 2*(2*(2*coût(n-3)+1)+1)+1                                   
            = ....                                                        
            = 2*(2*(2*(2*(....(2*coût(0)+1)...)+1)+1)+1                   

Pas vraiment plus clair, il est vrai. Prenons un exemple alors. Prenons n=3 :

    coût(0)=0                                                             
    coût(1)=2*coût(0)+1=1                                                 
    coût(2)=2*coût(1)+1=3                                                 
    coût(3)=2*coût(2)+1=7                                                 

Ca a l'air de donner du 2^n-1. On aurait donc coût(n)=2^n-1

Oui, peut-être, mais ça il va falloir le prouver. Et puisque depuis le début on fait de la récursivité, et bien continuons en utilisant la récursivité pour démontrer cela.

C'est tout de même bien pratique la récursivité : si vous savez démontrer que ça marche à 2 endroits, vous savez démontrer que ça marche partout.

Au rang 0 : coût(0)=0 c'est clair, rien à démontrer

Supposons que coût(n)=2^n-1 est vérifiée au rang n. Montrons que cela est aussi vérifiée au rang n+1 (coût(n+1)=2^(n+1)-1 ?)

On a vu que coût(n)=2*coût(n-1)+1 qui est toujours vérifié, donc :

    coût(n+1) = 2*coût(n)+1                                               
              = 2*(2^n-1)+1                                               
              = 2^(n+1)-2+1                                               
              = 2^(n+1)-1                                                 

coût(n+1) est donc vérifiée, et par suite du principe de récurrence, coût(n) est aussi vérifiée. Il faut donc 2^n-1 déplacements de disques lorsque l'on joue avec n disques.

 

III.2 Retour à la légende

Revenons à nos moines avec leur 64 disques. Cherchons combien de temps leur faudra-t'il pour atteindre le nirvana et le temps qu'il nous reste à vivre avant la fin du monde.

Disons qu'il leur faut à peu prés 4 secondes pour déplacer 1 disques (n'oublions pas que leur jeu était en grandeur nature). Ca fait donc 3600/4=900 mouvements par heure. Imaginons qu'ils jouent jour et nuit à ce jeu -> 900*24h = 21600 par jour. Mais ils ont 64 disques, d'où 2^64-1 mouvements, soit ~ 1,8*10^19 mouvements à faire.

On divise ce nombre par le nombre de mouvements par jour :

1,8*10^19 / 21600 = 8,5*10^14 jours pour finir le jeu.

 

[Dionys]