Récréation
Ce jeu célèbre a été inventé par le mathématicien français LUCAS et publié en 1892.
On considère trois tiges plantées dans une base. Au départ, sur la première tige sont enfilées N disques de plus en plus étroits. Le but du jeu est de transférer les N disques sur la troisième tige en conservant la configuration initiale.
On ne peut déplacer qu'un seul disque à la fois et il est interdit de poser un disque sur un autre plus petit.
La seconde tige est utilisée pour les stockages intermédiaires.
Il existe plusieurs algorithmes pour résoudre ce problème. Le plus évident (et le plus simple à programmer) utilise une méthode récursive.
Méthode récursive :
On suppose que l'on sait placer les N − 1 premiers disques sur la tige 2 en utilisant la tige 3 comme intermédiaire.
On déplace le Nième disque de la tige 1 vers la tige 3.
On déplace les N − 1 de la tige 2 vers la tige 3 en utilisant la tige 1 comme intermédiaire.
On réitère tant que N n'est pas nul.
En Java, on peut écrire la procédure récursive sous la forme :
| public void Transfert(int N, byte Orig, byte Dest, byte Inter) { if (N > 0){ Transfert(N-1, Orig, Inter, Dest ); Deplace(Orig, Dest); Transfert(N-1, Inter, Dest, Orig);}} |
On montre qu'avec cet algorithme, il faut effectuer 2N − 1 opérations pour effectuer le transfert.
Utilisation :
Le programme permet soit la résolution automatique du problème soit la résolution manuelle.
On peut choisir le nombre de disques N qui doit être compris entre 3 et 10.
En mode automatique le curseur permet de régler la vitesse des déplacements.
Le bouton [Départ] permet de revenir à tout moment à la configuration initiale.
En mode manuel, cliquer avec la souris dans le rectangle blanc situé sous la tige du disque que l'on désire déplacer, glisser le curseur de la souris (en maintenant le bouton enfoncé) vers le rectangle blanc situé sous la tige d'arrivée et relâcher le bouton pour effectuer le transfert. Le programme ne permet pas de déplacer un disque sur un disque plus petit que lui.
S'il n'existe pas de tours à Hanoï on y trouve quelques jolies pagodes.
Voici la plus petite et sans doute la plus originale.