La première est le point de départ et comporte un certain nombre de disques empilés selon leur taille(le plus grand dessous).
La seconde sert de « pont » pour faire passer les disques au point d'arrivée.
La troisième et dernière tige est le point d'arrivée, où l'on doit apporter tous les disques.
Pour l'instant rien de difficile, pour compliquer cela, on interdit de poser un disque sur un disque de taille inférieur. Lorsque les disques arrivent à la tige d'arrivée, il faut donc qu'ils soient dans le même ordre qu'ils étaient sur la tige de départ. On comprends alors l'importance de la tige intermédiaire.
Le but du jeu est donc de faire passer tous les disques de la première à la troisième tige, en faisant le moins de déplacements.
Le jeu des tours de Hanoï en javascript
Je vous ai ici programmé le jeu en javascript, pour vous que puissiez mieux le comprendre, vous pouvez selectionner votre nombre de disques pour faire varier la difficulté de 1 (pour commencer en douceur) à 9 (pour les plus patients). Vous devez faire le nombre minimum de déplacements pour gagner... Bonne chance !
Remarque : Il ne faut pas faire glisser un disque avec la souris pour le déplacer, mais cliquer sur la tige de départ puis sur la tige d'arrivée.
Nombre de déplacements :
La méthode
Alors ça y est vous avez compris ? Voici la solution, si D(n) est le nombre de déplacements pour n disques :
Pour 1 disque, la réponse est simple, il suffit de faire 1 déplacement soit D(1) = 1.
Pour n + 1 disques, il faut d'abord effectuer D(n) déplacements pour faire passer les n plus petits disques sur la tige « pont ». On fait ensuite passer le grand disque sur la tige d'arrivée, ce qui fait 1 déplacement de plus. Puis il ne nous reste plus qu'à déplacer les n disques sur le grand disque, cela nécessite encore D(n) déplacements. Au total, on a fait D(n) + 1 + D(n) = 2D(n) + 1 déplacements. D'où la relation D(n + 1) = 2D(n) + 1.
Avec ces deux égalités, on peut connaitre tous les D(n) :
D(2) = 2 × D(1) + 1 = 2 × 1 + 1 = 3
D(3) = 2 × D(2) + 1 = 2 × 3 + 1 = 7
etc...
On peut aussi démontrer par récurrence que .
En effet, D(1) = 1 et si l'égalité est vraie au rang n, alors .
Voilà comment fait le script pour calculer le nombre de déplacements minimum.
Cette page est conforme aux normes du W3C - Auteur : Frédéric WANG - Dernière mise à jour : mardi 24 juin 2003
