Résolution de la tour de Hanoï
La tour de Hanoï est un jeu inventé par le mathématicien français Édouard Lucas.
Les règles sont simples :
- le jeu est organisé autour de trois bâtons de bois que l'on nommera \(a\), \(b\) et \(c\) ;
- sur ces bâtons, on glisse des pièces circulaires de diamètres différents. Le nombre de pièces est appelé \(n\) ;
- les pièces doivent toujours être empilées dans un ordre décroissant : il est interdit de poser une grande pièce sur une petite ;
- à chaque étape on déplace une pièce d'un bâton à l'autre ;
- initialement, les pièces sont sur le bâton \(a\). Le but du jeu est de les amener sur le bâton \(c\).
A vous de jouer
Les trois bâtons sont modélisés par des instances de la classe Pile : a, b et c.
Interface de la classe Pile
-
p = Pile(): crée une pile vide et l'affecte à la variablep; -
p.est_vide(): renvoie le booléen indiquant si la pilepest vide ; p.empile(x): empile l'élémentxdans la pilep;p.depile(): dépile un élément de la pilepsi elle n'est pas vide et le renvoie. Provoque une erreur si la pile est vide.
Remarques
-
La classe
Piledispose d'une méthode qui permet de dessiner la pile. -
La classe empêchera d'empiler une pièce sur une pièce plus petite.
Des pièces de diamètres \(140\), \(120\), \(100\), \(80\), \(60\) et \(40\) sont empilés sur le bâton a. Les bâtons b et c sont initialement vides.
>>> a = Pile()
>>> b = Pile()
>>> c = Pile()
>>> a.empile(140)
>>> a.empile(120)
>>> a.empile(100)
>>> a.empile(80)
>>> a.empile(60)
>>> a.empile(40)
>>> a
'140|120|100|80|60|40|'
>>> b
''
>>> c
''
Les différentes questions sont indépendantes.
Déplacer 1 pièce
Compléter le code de la procédure deplace_1 qui prend en paramètres la pile de depart et la pile d'arrivee, et qui permet de transférer une pièce de l'une vers l'autre.
Exemples
On se place dans l'état initial décrit plus haut. L'exemple ci-dessous permet de déplacer la pièce au sommet de la a sur la b.
>>> deplace_1(a, b)
>>> a
`140|120|100|80|60|`
>>> b
'40|'
L'animation se lancera ici
Déplacer 2 pièces
Écrire une procédure deplace_2 qui prend en paramètres \(3\) piles depart, arrivee et intermediaire et qui déplace les \(2\) pièces au sommet du bâton de depart vers le bâton d'arrivee en utilisant le bâton intermediaire.
Exemple
On se place dans l'état initial décrit plus haut. L'appel ci-dessous permet de déplacer les \(2\) pièces au sommet de la pile a vers la pile c, en s'aidant de la pile b comme intermédiaire :
>>> deplace_2(a, c, b)
>>> a
`140|120|100|80|`
>>> b
''
>>> c
'60|40|'
Indication
On pourra réutiliser la procédure deplace_1 qui est déjà chargée en mémoire.
# Tests (insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)
L'animation se lancera ici
Déplacer n pièces
Un stratégie de résolution optimale, qui résout le problème en un nombre minimal de déplacements, repose sur l'observation suivante. Transporter \(n\) pièces du bâton \(a\) vers le \(c\) nécessite de :
-
transporter les \(n - 1\) pièces du dessus du bâton \(a\) vers le \(b\) ;
-
déplacer la plus grande pièce du bâton \(a\) vers le \(c\) ;
-
transporter les \(n - 1\) pièces du bâton \(b\) vers le \(c\).
L'illustration ci-dessous1 illustre la résolution du problème dans le cas \(n = 4\) :
Écrire une procédure récursive deplace_n qui prend en paramètres le nombre n de pièces à déplacer et \(3\) piles depart, arrivee, intermediaire et qui déplace les n pièces du sommet du bâton de depart vers le bâton d'arrivee en utilisant le bâton intermediaire.
On pourra réutiliser les procédures deplace_1 et deplace_2 qui sont déjà chargées en mémoire.
Aide
Les solutions pour \(n = 1\) et \(n = 2\) sont triviales : voir questions précédentes.
Exemples
On se place dans l'état initial décrit plus haut. L'appel ci-dessous permet de déplacer les \(4\) pièces au sommet du bâton a vers le bâton c, en s'aidant du bâton b comme intermédiaire :
>>> deplace_n(4, a, c, b)
>>> a
`140|120|`
>>> c
'100|80|60|40|'
# Tests (insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)
L'animation se lancera ici
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)