Les tours de Hanoï

Un problème bien connu qui se résout très facilement par un algorithme récursif (et difficilement par un algorithme itératif, comme nous le verrons plus loin) est "les tours de Hanoi". La légende dit que dans un temple de Hanoï, à l'origine du monde, 64 disques de diamètre croissant étaient empilés sur un taquet. Deux autres taquets sont disponibles, qui sont utilisés pour déplacer les disques, la condition étant qu'un disque d'un certain diamètre ne peut pas être placé au dessus d'un disque de diamètre inférieur. Donc, les disques sont toujours empilés dans un certain ordre: les plus grands sont toujours en bas du taquet. La légende dit aussi que des moines sont en train de déplacer les 64 disques vers l'un des deux autres, au rythme de un par seconde et quand ils auront terminé, ce sera la fin du monde.

En faisant un petit calcul rapide, on a 2⁶⁴-1 secondes, ce qui correspond à 585 milliards d'années et sachant que l'âge de l'univers est de seulement 15 milliards d'années, on a encore de la marge : ouf ! On l'a échappé belle! :)))

Voyons maintenant la programmation de cet algorithme.

On décide que les disques ont un numéro correspondant à leur diamètre, et que les diamètres vont de 1 à 64.

Nous allons d'abord étudier deux cas concrets de déplacement: comme d'habitude, d'abord on observe, ensuite on programme l'algorithme.

Soit deux disques à déplacer du taquet 1 vers le 3.

Le taquet final est 3, celui initial est 1, donc celui intermédiaire est 2.

Opérations de déplacement :

- disque 1 de taquet 1 vers taquet 2

- disque 2 de taquet 1 vers taquet 3 ---> milieu

- disque 1 de taquet 2 vers taquet 3

Soit trois disques à déplacer du taquet 1 vers le 3.

Le taquet final est 3, celui initial est 1, donc celui intermédiaire est 2.

Maintenant on doit se retrouver avec les deux premiers disques sur le taquet 2, de façon à pouvoir déplacer le disque 3 vers la taquet 3 et ensuite les deux premiers du taquet 2 vers le taquet 3.

Opérations de déplacement :

- disque 1 de taquet 1 vers taquet 3

- disque 2 de taquet 1 vers taquet 2

- disque 1 de taquet 3 vers taquet 2

- disque 3 de taquet 1 vers taquet 3 ---> milieu

- disque 1 de taquet 2 vers taquet 1

- disque 2 de taquet 2 vers taquet 3

- disque 1 de taquet 1 vers taquet 3

En regardant bien les déplacements effectués, on constate les choses suivantes :

- si on a "n" disques à déplacer :

- on déplace "n-1" disques vers le taquet intermédiaire

- on déplace le disque "n" du taquet initial vers le taquet final ---> milieu

- on déplace les "n-1" disques du taquet intermédiaire vers le taquet final

On peut d'ores et déjà en déduire l'algorithme :

procedure TForm1.Button1Click(Sender: TObject);
 procedure hanoi(nb_disques, depart, arrivee: integer);
 var intermediaire: integer;
 begin
  if nb_disques = 1 then
 memo1.lines.add('On déplace un disque de ' +
 inttostr(depart) + ' vers ' + inttostr(arrivee))
 else
 begin
 intermediaire := 6 - depart - arrivee;
 hanoi(nb_disques - 1, depart, intermediaire);
 memo1.lines.add('On déplace un disque de ' +
 inttostr(depart) + ' vers ' + inttostr(arrivee));
 hanoi(nb_disques - 1, intermediaire, arrivee);
 end;
 end;
begin // deplacer 4 disques
 hanoi(4, 1, 2);
end;
 

Télécharger le code source Delphi