Les tours de Hanoï

tour hanoiLa légende

Selon une légende très
ancienne, il existe un
temple où les moines
sont chargés de veiller
sur 64 disques sacrés.
Les disques, qui sont tous
de taille différente, forment
une tour. Comme ils sont précieux et très fragiles, un disque ne peut être
placé sur un disque plus petit.

Hélas, le jour vient où quelques travaux dans le temple sont nécessaires
et les disques doivent être déplacés. Ils sont très lourds et ne peuvent
donc être transportés qu’un par un.
De plus, il n’y a qu’un seul endroit assez sacré pour les stocker.
Les moines commencent donc à déplacer les disques de la tour d’origine
vers la nouvelle place et l’endroit intermédiaire, gardant toujours chacune
des trois piles en ordre (le disque le plus large en bas, le moins large en haut).
Alors qu’ils travaillent, les moines gardent en tête la terrible prophétie :
« Le temple s’écroulera avant que les disques ne soient mis en place. »

Qu’en pensez-vous?

A vous de jouer !

La jeu de la Tour de Hanoï est utilisée dans la recherche en psychologie cognitive
au travers de la résolution de problème.
Sensible aux dysfonctionnements frontaux et pré-frontaux, le jeu peut être
utilisé comme test pour évaluer l’intelligence fluide à travers les fonctions
exécutives : planification, mémoire de travail (stockage temporaire
d’informations et leur traitement)
, inhibition.
La performance à la tour d’Hanoï dépend des capacités d’inhibition,
des capacités de la mémoire de travail (stockage temporaire et traitement d’informations) et de la mémoire procédurale (gestes).

Il existe un jeu de réflexion basé sur cette légende 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 ».
Le but du jeu est de bouger tous les disques de la pile du centre vers
un nouvel endroit en se servant de la position intermédiaire et en
respectant les règles suivantes :

  • On ne peut déplacer qu’un disque à la fois.
  • On ne peut déplacer un disque qui se trouve sous un autre.
  • Un disque ne peut être déposé sur un disque plus petit.

Quel est le nombre minimum de déplacements nécessaires
pour bouger une pile de  » n «  disques?

Bien sûr, si n = 1, un coup suffit ! Si n = 2, c’est aussi assez facile :
On bouge le petit disque en position intermédiaire, puis le grand sur
l’endroit final. Enfin, on pose le petit disque sur le grand.
Finalement, on a déplacé la pile en 3 coups.
Et si n est plus grand ?

Jeu en ligne sur le site de l’université de Rouen

Nous vous proposons de commencer avec 3 disques afin de voir
en combien de « coups » vous pouvez déplacer la pile.
Quand vous penserez avoir trouvé le nombre de coups minimum,
passez à 4 disques.(…)

logo LMRSlogo Maths pour tous

Il existe plusieurs procédures : une procédure récursive (1) mais également
une procédure itérative (2) plus simple pour résoudre le problème des tours
de Hanoï, et ce de façon optimale.
Elle consiste à effectuer successivement les deux déplacements suivants,
en désignant par A, B, C les trois tours (de gauche à droite) :

hanoit–  déplacer le plus petit disque d’un emplacement à l’emplacement suivant (de A vers B, de B vers C, de C vers A, par exemple) ;
– déplacer un autre disque ;

Ensuite, poursuivre itérativement ces deux déplacements jusqu’à ce que
la tour complète soit déplacée, le dernier déplacement se limitant
alors à celui du plus petit disque sur le sommet de la tour.
L’action « déplacer un autre disque » est non ambiguë puisque,
en dehors du plus petit disque, un seul mouvement de disque est possible.

 

(1) procédure qui, lorsqu’on l’exécute, va faire appel à elle-même
(récursivement) afin de mener à bien l’exécution.
Ex : lorsqu’on est en train de déclarer une procédure récursive,
on va utiliser cette même procédure à l’intérieur de son corps.
La résolution est vue comme un algorithme récursif à programmer.

(2) méthode utilisé pour résoudre un problème : en débutant par
le choix d’un point initial (première ébauche de la solution),
la méthode procède par itérations (répétitions) déterminant
une succession de solutions approximatives s’approchant
graduellement de la solution recherchée

 

2 réflexions au sujet de « Les tours de Hanoï »

Répondre à Andrieu Annuler la réponse

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *