Informatique · Algorithmes
Tours de Hanoï : dix niveaux
De 1 à 10 disques : jouez, observez la récursivité et essayez d’atteindre le minimum de déplacements.
Déplacez tous les disques de A vers C. Touchez un piquet pour choisir son disque supérieur, puis le piquet d’arrivée. Déplacez un seul disque à la fois et ne posez jamais un grand disque sur un plus petit. Au clavier : Tab pour choisir le piquet, Entrée ou Espace pour l’activer.
Déplacements effectués—
Minimum depuis le départ—
Minimum encore nécessaire—
Record manuel sur cet appareil—
Partie manuelle
Lancer et Un pas continuent depuis la position actuelle : un choix différent n’impose pas de recommencer. Pause laisse finir le déplacement en cours. Recommencer efface seulement la partie actuelle, pas les records.
Cet appareil ne prend pas en charge l’animation : les déplacements restent disponibles pas à pas.
Derniers déplacements
- Aucun déplacement effectué.
Les 12 derniers déplacements sont affichés ; Annuler permet de revenir jusqu’au début de la partie.
Niveaux terminés manuellement
Les records manuels restent dans ce navigateur, si disponible. Aucun compte ni envoi des scores. Tous les niveaux sont déjà accessibles.
Pourquoi le minimum est-il 2ⁿ − 1 ?
Pour déplacer n disques de A vers C, libérez d’abord le plus grand en déplaçant les n−1 disques au-dessus de lui sur B. Déplacez ensuite le disque n de A vers C, puis les n−1 disques de B vers C.
- Déplacez n−1 disques de A vers B en utilisant C comme appui.
- Déplacez le disque n de A vers C.
- Déplacez n−1 disques de B vers C en utilisant A comme appui.
M(0) = 0
M(n) = 2 × M(n−1) + 1 = 2n − 1
Le même problème réapparaît avec un disque de moins : c’est la récursivité. Avec zéro disque, ne faites rien. Chaque disque ajouté double le minimum précédent et ajoute un déplacement. Les indices et la solution guidée utilisent cette même stratégie, adaptée à la position actuelle.
| Disques | Minimum de déplacements |
|---|---|
| 1 | 1 |
| 2 | 3 |
| 3 | 7 |
| 4 | 15 |
| 5 | 31 |
| 6 | 63 |
| 7 | 127 |
| 8 | 255 |
| 9 | 511 |
| 10 | 1023 |