|
Hanoï
°
Tour de Hanoï. – Solitaire
inventé par Édouard Lucas (1842-1891) et vendu comme jouet dès
1883. Il est composé d'une planchette horizontale et de trois chevilles
verticales.
Au départ, huit disques de grandeur décroissante de bas en haut
sont enfilés sur une cheville. Il s'agit de transférer les disques sur l'une
des deux autres chevilles en déplaçant un disque à la fois et en plaçant
toujours un disque sur un autre plus grand, tout en faisant le moins de
mouvements possible. Pour déplacer les huit disques d’une tour, il faut 255
mouvements au minimum.
Le problème peut être généralisé avec n
disques. Le nombre minimum de mouvements nécessaires est établi par la formule
2n - 1.
Le tableau suivant précise le nombre de coups en bases 2 et
10 selon que la tour comprend de un à huit disques.
|
Disques |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
Base 2 |
1 |
11 |
111 |
1111 |
11 111 |
111 111 |
1 111 111 |
11 111 111 |
|
Base 10 |
1 |
3 |
7 |
15 |
31 |
63 |
127 |
255 |
La tour de Brahma est une version de la
tour de Hanoï.
© Charles-É. Jean
Index
: H
|
