Jouez. Anticipez. Comprenez.
Jouez avec 3 à 5 disques, demandez un indice adapté à votre position et découvrez la récursion avec deux courtes animations. Consultez un exemple pas à pas à tout moment.
Jouer aux tours de HanoïDéplacez la petite pile pour libérer le plus grand disque.
Choisissez la colonne de départ puis celle d’arrivée. Les numéros indiquent la taille : 1 est le plus petit disque. Annulez un coup ou recommencez pour essayer autrement.
Choisissez la colonne de départ, puis celle d’arrivée.
Les indices partent de votre position et ne déplacent aucun disque. Un détour légal reste résoluble.
Pensez d’abord au plus grand disque. Dans cet exemple à quatre disques, trois petits disques le bloquent. Résolvez ce petit problème avant de déplacer le disque 4.
Déplacez les disques 1, 2 et 3 de A vers B en utilisant C comme colonne auxiliaire. Le disque 4 reste sur A : C est libre et le disque 4 est accessible.
Déplacez le disque 4 de A vers C. Ce seul coup place le plus grand disque à sa position finale.
Déplacez les disques 1, 2 et 3 de B vers C en utilisant A comme colonne auxiliaire. Ils reposent sur le disque 4 : le problème est résolu.
Chaque petite pile suit le même plan : écarter les disques au-dessus du plus grand, déplacer celui-ci, puis ramener la petite pile dessus. Avec un seul disque, déplacez-le directement. C’est la récursion : les rôles des colonnes changent à chaque sous-problème.
Ces exemples séparés à quatre disques préservent votre partie. Faites une pause, avancez pas à pas, répondez à une question ou affichez l’explication.
Regardez trois petits disques libérer le disque 4. Prévoyez où ils doivent se trouver avant son déplacement.
Exemple séparé à quatre disques
Objectif : déplacer 3 disques de A vers B, avec C comme colonne auxiliaire.
Libérez d’abord le passage : déplacez les trois disques du dessus de A vers B.
Étape 0 sur 8
Le disque 4 est déjà sur C. Il reste le même problème avec trois disques et de nouveaux rôles pour les colonnes.
Exemple séparé à quatre disques
Objectif : déplacer 3 disques de B vers C, avec A comme colonne auxiliaire.
Le disque 4 reste sur C. Résolvez maintenant les trois disques de B vers C.
Pour déplacer trois disques de B vers C avec A, où va d’abord le disque 1 ?
Étape 0 sur 7
Ces exemples commencent avec tous les disques sur A et se terminent sur C. Ouvrez-les directement : votre partie reste inchangée.
T(n) = 2T(n − 1) + 1 = 2ⁿ − 1
La solution classique déplace deux fois la petite pile et une fois le plus grand disque : T(n) = 2T(n − 1) + 1. Un disque demande un coup, donc le minimum pour n disques est 2ⁿ − 1.
3 disques : 7 coups. 4 disques : 15 coups. 5 disques : 31 coups.
Départ : tous les disques sur A. Arrivée : C. Le disque 1 est le plus petit.
Départ : tous les disques sur A. Arrivée : C. Le disque 1 est le plus petit.
Départ : tous les disques sur A. Arrivée : C. Le disque 1 est le plus petit.
Toute position respectant les tailles peut atteindre C. Revenir à une position connue est une boucle, pas une impasse. La formule s’applique au départ classique, pas aux coups restant depuis une position quelconque. Demandez un indice adapté à votre position.