Aller au contenu
Omnikalc

Calculateur des tours de Hanoï : combien de déplacements et combien de temps pour un nombre de disques

Saisissez le nombre de disques et la durée d’un déplacement pour obtenir le nombre minimal de déplacements des tours de Hanoï, la durée de résolution et le nombre de déplacements de n’importe quel disque.

Mis à jour le
Vos paramètres

Valeur hors limites

s

Valeur hors limites

Valeur hors limites

Résultats

Nombre minimal de déplacements

1 048 575

Durée pour résoudre le casse-tête
145:38:08
Déplacements du plus petit disque
524 288
Déplacements du disque suivi
4 096
Plus grand nombre de disques résolvable en 80 ans de jeu continu
32

Les tours de Hanoï sont un casse-tête classique où n disques se déplacent entre trois piquets. Le calculateur des tours de Hanoï donne le nombre minimal de déplacements 2ⁿ − 1, la durée de résolution, les déplacements du plus petit disque, ceux de n’importe quel disque et le plus grand casse-tête résolvable en une vie.

Comment se fait le calcul

  • Saisissez le nombre de disques sur le premier piquet. Le casse-tête classique à 3 piquets se résout en déplaçant un disque à la fois, sans jamais poser un grand disque sur un plus petit.
  • Saisissez la durée d’un déplacement en secondes, pour obtenir le temps total de résolution.
  • Saisissez le numéro d’un disque à suivre, 1 pour le plus petit. Le plus petit disque bouge un coup sur deux, et le plus grand ne bouge qu’une fois.
  • Le calculateur donne le nombre minimal de déplacements 2ⁿ − 1, la durée, le nombre de déplacements du plus petit disque 2ⁿ⁻¹, ceux du disque suivi 2ⁿ⁻ᵏ et le plus grand casse-tête résolvable en 80 ans.

Exemple

Avec 20 disques, le nombre minimal de déplacements est de 2²⁰ − 1 = 1 048 575. À une demi-seconde par déplacement, le casse-tête prend 6 jours 1 heure 38 minutes. Le plus petit disque bouge 2¹⁹ = 524 288 fois. Le huitième disque bouge 2¹² = 4 096 fois. Avec un jeu continu de 80 ans à une demi-seconde par déplacement, vous pourriez résoudre un casse-tête de jusqu’à 32 disques, qui demande 4 294 967 295 déplacements.

Pourquoi c’est utile

Le calculateur aide les élèves, les enseignants et les amateurs de casse-têtes à voir la vitesse de croissance d’une exponentielle, à préparer une démonstration en classe avec un nombre de disques résolvable à temps et à illustrer la récursivité en informatique. Il montre pourquoi chaque disque ajouté double le travail.

À savoir

La formule donne le nombre minimal de déplacements du casse-tête à trois piquets avec les règles standards. Avec quatre piquets ou plus, le minimum est bien plus petit et donné par la conjecture de Frame-Stewart. Pour une démonstration, prévoyez du temps pour les erreurs, car la durée réelle est plus longue que le minimum. Le nombre de disques est limité à 50.

Outils liés

Le calculateur de logarithme inverse une puissance de deux, celui de la croissance exponentielle modélise des doublements répétés, celui des séries arithmético-géométriques somme des suites voisines, et celui de Fibonacci explore une autre récurrence célèbre.

Questions fréquentes

Qu’est-ce que les tours de Hanoï ?

Les tours de Hanoï sont un casse-tête avec trois piquets et une pile de disques de tailles différentes sur le premier piquet, le plus grand en bas. Le but est de déplacer toute la pile sur un autre piquet, un disque à la fois, sans jamais poser un grand disque sur un plus petit. Le mathématicien français Édouard Lucas l’a inventé en 1883.

Combien de déplacements faut-il ?

Le nombre minimal de déplacements pour n disques est 2ⁿ − 1. Pour déplacer n disques, on déplace n − 1 disques sur le piquet libre, on déplace le plus grand disque, puis on replace les n − 1 disques par-dessus. Cela donne la récurrence M(n) = 2 × M(n − 1) + 1, qui se résout en 2ⁿ − 1. Chaque disque en plus double le travail.

Quelle est la légende des 64 disques ?

Une légende raconte que des moines déplacent une tour de 64 disques d’or dans un temple, et que le monde finira quand ils auront terminé. Le casse-tête demande 2⁶⁴ − 1, soit environ 1,8 × 10¹⁹ déplacements. À un déplacement par seconde, il faudrait environ 585 milliards d’années, soit plus de 40 fois l’âge de l’univers.

À quelle fréquence chaque disque bouge-t-il ?

Le plus petit disque bouge un coup sur deux, soit 2ⁿ⁻¹ fois au total. Le disque numéro k, compté depuis le plus petit, bouge 2ⁿ⁻ᵏ fois, et le plus grand bouge une fois. La somme de tous ces déplacements est 2ⁿ − 1. Le plus petit disque se déplace toujours dans le même sens autour des trois piquets.

Ce calculateur vous a-t-il été utile ?

Merci pour votre avis !

Résultats indicatifs fournis à titre d'information. Ils ne remplacent pas l'avis d'un professionnel.