Situation de départ :
| | |
| | |
---+--- | |
| | |
-----+----- | |
================================================
Situation d'arrivée :
| | |
| | |
| | ---+---
| | |
| | -----+-----
================================================
( sachant qu'il y a évidemment plus de 2 disques).
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é.
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 !!
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.
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 :
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".
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.
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]