Les tours de Hanoï#

Dans le jeu des tours de Hanpoï, \(n\) disques sont empilés par taille décroissante sur un premier poteau. Le but du jeu est de déplacer ces disques vers un second poteau en les plaçcant dans le même ordre, c’est à dire par taille décroissante. On dispose pour cela d’un troisième poteau.

Les règles du jeu sont les suivantes:

  • on ne déplace qu’un disque à la fois,

  • on ne peut déplacer qu’un disque situé en haut d’une pile,

  • on ne peut pas déposer un disque sur un disque de plus petite taille.

On donne ci-dessous la disposition des disques en début et fin de partie.

../_images/hanoi_debut_partie.svg

Début de partie des tours de hanoï avec 4 disques#

../_images/hanoi_fin_partie.svg

Fin de partie des tours de hanoï avec 4 disques

Étude de cas particuliers#

  1. Proposer une solution du jeu avec 2 disques.

  2. Donner une solution du jeu avec 3 disques. On pourra représenter les différentes étapes par des schémas.

  3. Dans le cas des trois disques, repérer dans votre schéma les étapes correspondant à la resolution du problème avec 2 disques.

  4. En déduire un algorithme de résolution du jeu avec 3 disque en notant la resolution du jeu à 2 disque par hanoi(2, x -> y) où x et y désignent des poteaux.

Étude du cas général#

On suppose que l’on sait résoudre le problème avec \(n-1\) disques. On note cette résolution comme précédemment par hanoi(n-1, A -> C) lorsqu’on déplace les disques du poteau A vers le poteau C.

../_images/hanoi_n_disques.svg

Jeu des tours de Hanoï avec \(n\) disques#

  1. Représenter schématiquement la résolution du jeu avec \(n\) disques.

  2. Écrire un algorithme qui s’appuie sur la résolution du jeu avec \(n-1\) disques pour résoudre le jeu avec \(n\) disques.

Programmation en Python#

Le programme Python du jeu des tours de Hanoi utilisent les structures de données suivantes:

  • 3 piles pour représenter les poteaux A, B et C avec leurs disques,

  • des nombres entiers pour représenter les disques

Au début de la partie, la pile A contient tous les disques, c’est à dire les nombres entiers rangés par ordre croissant (le plus petit est au sommet de la pile). Les pilse B et C sont vides.

À la fin du programme, La pile C contient les disques, c’est à dire les nombres entiers rangés dans l’ordre croissant, le plus petit étant au sommet de la pile. Les piles A et B sont vides.

Le programme à compléter contient des fonctions:

  • la fonction deplacer(p1,p2) qui déplace un disque d’une pile p1 à une autre pile p2.

  • l’import des fonctions pour créer et manipuler des piles.

Ouvrir le notebook de code fc4e-2297352 qui contient le programme puis compléter la fonction tout_hanoi pour résoudre le jeu.