ArithmétiqueNotion · Glossaire
problème des tours de Hanoï
Le problème des tours de Hanoï consiste à transférer une tour de n disques de diamètres distincts, rangés du plus grand au plus petit, entre trois tiges, en ne déplaçant qu’un disque supérieur à la fois et sans jamais poser un disque sur un plus petit. Pour libérer le plus grand disque, il faut d’abord déplacer récursivement tous ceux qui le surmontent vers la tige auxiliaire. Avec ces règles et trois tiges, le minimum est 2ⁿ − 1 déplacements ; le problème illustre ainsi la récursivité en algorithmique et le dénombrement.
Sommaire
Ce que vous allez apprendre
- Identifier les trois règles qui rendent un déplacement légal.
- Reproduire une solution minimale à trois disques en sept déplacements.
- Relier la stratégie récursive à la récurrence T(n) = 2T(n − 1) + 1.
- Distinguer une solution légale d'une solution minimale.
En clair
Imaginez trois tiges et une tour de disques, du plus large en bas au plus petit en haut. Il faut transporter la tour vers une autre tige. À chaque geste, seul le disque visible au sommet d'une pile peut bouger. Il est interdit de déposer un grand disque sur un plus petit.
La difficulté vient de ce détour obligé : pour déplacer le plus grand disque, tous les autres doivent d'abord libérer le passage. La même situation réapparaît alors avec une tour plus petite.
Définition
Le problème des tours de Hanoï porte sur trois tiges et une tour de n disques de diamètres distincts, rangés du plus grand au plus petit. Le nombre n désigne le nombre de disques. La tour part d'une tige et doit être reconstruite sur une autre ; la troisième sert d'intermédiaire.
Un déplacement prend exactement le disque supérieur d'une pile. Ce disque peut rejoindre une tige vide ou être posé sur un disque plus grand, jamais sur un disque plus petit. La stratégie récursive consiste à déplacer les n − 1 disques supérieurs vers la tige intermédiaire, à déplacer le plus grand vers la destination, puis à transférer les n − 1 disques sur celui-ci.
Si T(n) note le minimum de déplacements pour n disques, cette décomposition donne , avec . Elle conduit à . Le résultat compte un minimum : une suite légale qui comporte des détours peut être plus longue.
Un exemple, pas à pas
Prenons trois disques, numérotés 1, 2 et 3 du plus petit au plus grand. Ils occupent d'abord la tige A ; la tige B sert d'intermédiaire et la tige C est la destination. Le minimum attendu est 23 − 1 = 7 déplacements.
1. Déplacer le disque 1 de A vers C.
2. Déplacer le disque 2 de A vers B.
3. Déplacer le disque 1 de C vers B.
4. Déplacer le disque 3 de A vers C.
2. Déplacer le disque 2 de A vers B.
3. Déplacer le disque 1 de C vers B.
4. Déplacer le disque 3 de A vers C.
5. Déplacer le disque 1 de B vers A.
6. Déplacer le disque 2 de B vers C.
7. Déplacer le disque 1 de A vers C.
6. Déplacer le disque 2 de B vers C.
7. Déplacer le disque 1 de A vers C.
La tour est reconstruite sur C en 7 déplacements. Pour contrôler le minimum, il faut d'abord déplacer deux disques afin de libérer le disque 3, puis déplacer ce dernier, puis replacer deux disques : 3 + 1 + 3 = 7.
En pratique
Pour résoudre le casse-tête à la main, on traite d'abord la tour privée de son plus grand disque. Cette décomposition récursive est préférable à des essais au hasard dès que les retours en arrière se multiplient.
En algorithmique, la procédure appelle deux fois le même transfert sur une tour plus petite, séparé par le déplacement du plus grand disque. Une exécution itérative devient utile lorsque l'environnement ne convient pas aux appels récursifs, mais elle doit produire les mêmes déplacements légaux.
En dénombrement, la récurrence évite d'énumérer toutes les étapes pour prévoir la durée minimale. Pour 64 disques, elle donne exactement 264 − 1 déplacements : la croissance exponentielle suffit à expliquer le caractère astronomique de la légende.
À ne pas confondre
Le casse-tête mathématique ne doit pas être confondu avec la tour sacrée de la légende rapportée par Lucas. Le premier est défini par trois tiges, des disques et des règles vérifiables ; la seconde est un récit mettant en scène 64 disques. Le calcul 264 − 1 appartient au problème appliqué à cette taille, sans transformer la légende en règle supplémentaire.
Limites et pièges
La formule 2n − 1 suppose la version à trois tiges et le déplacement d'un seul disque supérieur à la fois. Ajouter une tige ou autoriser un autre geste change le problème ; il faut alors recalculer le minimum au lieu de réutiliser cette formule.
Pour un seul disque, le seuil charnière est immédiat : 21 − 1 = 1 déplacement. Avec zéro disque, la convention T(0) = 0 décrit une tour vide ; il n'existe aucun geste à effectuer.
Le nombre 2n − 1 n'est pas la longueur de toute solution légale. Si un disque effectue un détour autorisé, la tour peut encore atteindre la destination en davantage de gestes. Le minimum désigne la longueur de la plus courte solution, indépendamment des détours d'une solution particulière ; la formule 2n − 1 est atteinte par la stratégie récursive qui transfère chaque sous-tour sans détour.
Pour aller plus loin
Le dénombrement éclaire la manière de compter les déplacements sans les énumérer un à un.
La fiche algorithme replace la procédure récursive parmi les suites d'instructions qui résolvent un problème.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres