Tours de Hanoi
Les tours de Hanoï sont un célèbre casse tête inventé par Édouard Lucas.
Il consiste à déplacer $n$ disques de diamètres différents d'une tour de "départ" à une tour d' "arrivée" en passant par une tour "intermédiaire", tout en respectant les règles suivantes :
- on ne peut déplacer qu'un disque à la fois
- on ne peut placer un disque sur un disque plus petit que lui.
On suppose que cette dernière règle est également respectée dans la configuration de départ.
Une interface pour jouer aux tours de Hanoï.
Déplacez les cylindres par glisser/déposer.
Essayons de résoudre ce problème de façon optimale.
Donnez un algorithme récursif permettant de résoudre le problème.
Quelle est sa complexité ?
Peut-on faire mieux ?