Difference between revisions of "Tours de Hanoï"
| Line 20: | Line 20: | ||
Ce problème a toujours une solution. Il faut pour cela utiliser la troisième tour, comme lieu de | Ce problème a toujours une solution. Il faut pour cela utiliser la troisième tour, comme lieu de | ||
stockage temporaire. | stockage temporaire. | ||
| − | Soit U le nombre de coups, n le nombre de disques, on calcule U par : | + | Soit U le nombre de coups, n le nombre de disques, on calcule U par : U = 2<sup>n</sup> - 1. |
| + | |||
Ce qui donne pour résultats : | Ce qui donne pour résultats : | ||
{| | {| | ||
Revision as of 14:43, 8 August 2006
Le problème original
FIG. 6.2 – Tours de Hanoï : le problème classique
Problème
Ce problème a été inventé par le mathématicien Edouard LUCAS, d’après une légende hindoue. Selon cette légende, des moines sont gardiens de trois tours. 64 disques d’or concentriques, de plus en plus petits, sont empilés dans une des tours. Les moines doivent les transférer dans une autre tour, avec une règle unique : aucun disque ne doit être posé sur un plus petit. Quand il auront terminé, ce sera la fin du monde.
Une autre légende assure que ce puzzle était utilisé dans un temple pour la discipline mentale des aspirants à l’éveil. . . C’est plutôt dans cette optique que nous l’utiliserons aussi !
Régles
- 3 poteaux ;
- un certain nombre de disques ;
- un déplacement à la fois ;
- aucun disque ne peut être posé sur un disque plus petit.
Résolution
Ce problème a toujours une solution. Il faut pour cela utiliser la troisième tour, comme lieu de stockage temporaire. Soit U le nombre de coups, n le nombre de disques, on calcule U par : U = 2n - 1.
Ce qui donne pour résultats :
| Disques | Nombre de coups |
|---|---|
| 1 | 1 |
| 2 | 3 |
| 3 | 7 |
| 4 | 15 |
| 5 | 31 |
| ... | ... |
| 64 | 18 446 744 073 709 551 615 |
