Page d'accueil	encyclopedie-enligne.com en page d'accueil
Liste Articles: [0-A] [A-C] [C-F] [F-J] [J-M] [M-P] [P-S] [S-Z] | Liste Catégories | Une page au hasard | Pages liées

Tours de Hanoï

Les tours de Hanoï sont un jeu de réflexion consistant à déplacer des disques de diamètres différents d'une tour de « départ » à une tour d'« arrivée » en passant par une tour « intermédiaire » et ceci en un minimum de coups, tout en respectant la règle suivante : on ne peut placer sur un disque un autre disque plus grand que lui. On suppose que cette règle est également respectée dans la configuration de départ.

Il facile de démontrer par récurrence que si N est le nombre de disques, il faut 2^N - 1 coups au minimum pour parvenir à ses fins, ce qui augmente très rapidement le temps nécessaire pour résoudre ce problème.

Le jeu des tours de Hanoï est vu en algorithmique (programmation), où il offre un exemple de la puissance et de la lisibilité des programmes définis de façon récursive (un autre étant le tri arborescent. En effet, l'algorithme de résolution le plus simple se présente ainsi :

sub Déplacer (nombre, de, à, par)
 si nombre > 0 alors
 Déplacer nombre - 1, de, par, à;
 Bouger-un-disque de, à;
 Déplacer nombre - 1, par, à, de;
 fin-du-si
fin-du-sub

Liens externes

• Site de jeux
• Tours de Hanoï avec résolution