Les tours de Hanoï

On a trois pieux a, b et c ; sur le pieu a, on a empilé n disques de rayon décroissant en montant dans la tour ainsi constituée.

Problème : Déterminer la suite de manipulations pour passer les n disques sur le pieu b en déplaçant un seul disque à la fois entre deux des trois pieux, les rayons des disques décroissant vers le sommet de chaque tour.

Algorithme : Soit (p1,p2,p3) une permutation des trois pieux (a,b,c)
Pour amener N disques du pieu p1 sur le pieu p2

    1. manipuler pour passer (N-1) disques du pieu p1 sur le pieu p3,
    2. passer 1 disque du pieu p1 sur le pieu p2,
    3. manipuler pour passer (N-1) disques du pieu p3 sur le pieu p2.


Le nombre de manipulations f(n) pour déplacer n disques d'un pieu à un autre vérifie donc :
f(1) = 1 et f(n+1) = 2f(n) + 1 ou encore f(n+1) + 1 = 2[ f(n) + 1 ] donc f(n) = 2^n - 1

Le plan du programme Maple suit le plan ci-dessous ; pour chaque partie, un exemple du résultat est affichable.

I. Version élémentaire
L'ensemble des trois tours est symbolisé par une liste de trois listes,une pour chaque tour, dans lesquelles les disques sont représentés par leur rayon : une tour est une liste décroissante d'entiers éventuellement vide.
départ : [ [n,n-1, ..,1], [], []] ; arrivée : [ [], [n,n-1, ..,1], [] ]

Résultat montrant la suite des opérations effectuées pour n=4.
Chaque ligne représente l'état des trois tours à chaque étape.


Tour 1      Tour 2     Tour 3
[4,3,2,1]   []         []
[4,3,2]     []         [1]
[4,3]       [2]        [1]
[4,3]       [2,1]      []
[4]         [2,1]      [3]
[4,1]       [2]        [3]
[4,1]       []         [3,2]
[4]         []         [3,2,1]
[]          [4]        [3,2,1]
[]          [4,1]      [3,2]
[2]         [4,1]      [3]
[2,1]       [4]        [3]
[2,1]       [4,3]      []
[2]         [4,3]      [1]
[]          [4,3,2]    [1]
[]          [4,3,2,1]  []

II. Animation 2d
voir une simulation des manipulations

III. Animation 3d
voir une simulation des manipulations

Début