La Tour de Hanoi : Algorithme récursif

Question

Bien que je n'aie aucun problème à comprendre la récursion, je ne parviens pas à comprendre la solution récursive du problème de la tour de Hanoi. Voici le code de Wikipedia :

procedure Hanoi(n: integer; source, dest, by: char);
Begin
    if (n=1) then
        writeln('Move the plate from ', source, ' to ', dest)
    else begin
        Hanoi(n-1, source, by, dest);
        writeln('Move the plate from ', source, ' to ', dest);
        Hanoi(n-1, by, dest, source);
    end;
End;

Je comprends le cas de base et le concept de décomposer le problème en petits morceaux jusqu'à ce que vous soyez en mesure de déplacer un seul disque. Cependant, je n'arrive pas à comprendre comment les deux appels récursifs dans le cas non basique fonctionnent ensemble. Peut-être quelqu'un peut-il m'aider ? Merci.

Answer 1

En fait, le la section d'où vous avez pris ce code offre également une explication :

Pour déplacer n disques du pion A au pion C :

1. déplacer n1 disques de A à B. Cela laisse le disque n seul sur la cheville A.
2. déplacer le disque n de A à C
3. déplacer n1 disques de B à C pour qu'ils se trouvent sur le disque #n

C'est assez clair que vous devez d'abord enlever n 1 disques pour avoir accès à la n e. Et que vous devez d'abord les déplacer sur un autre piquet que celui où vous voulez que la tour complète apparaisse.

Le code dans votre post a trois arguments, en plus du nombre de disques : A source cheville, un destination et un temporaire sur lequel les disques peuvent être stockés entre les deux (où chaque disque de taille n 1 correspond).

La récursion se produit en fait deux fois, ici, une fois avant que les writeln et une fois après. Celui qui précède le writeln bougera n 1 disques sur la cheville temporaire, en utilisant la cheville de destination comme stockage temporaire (les arguments dans l'appel récursif sont dans un ordre différent). Après cela, le disque restant sera déplacé vers le piquet de destination et ensuite la deuxième récursion compulse le déplacement de la tour entière, en déplaçant les disques de la tour. n 1 tour de la cheville provisoire à la cheville de destination, au-dessus du disque. n.

Answer 2

Il y a un an j'ai eu un cours de programmation fonctionnelle et j'ai dessiné cette illustration pour l'algorithme. J'espère que cela vous aidera !

(0)  _|_         |          |
    __|__        |          |
   ___|___       |          |
  ____|____  ____|____  ____|____

(1.1) |          |          |
    __|__        |          |
   ___|___      _|_         |
  ____|____  ____|____  ____|____ (A -> B)

(1.2) |          |          |
      |          |          |
   ___|___      _|_       __|__
  ____|____  ____|____  ____|____ (A -> C)

(1.3) |          |          |
      |          |         _|_
   ___|___       |        __|__
  ____|____  ____|____  ____|____ (B -> C)

(2.1) |          |          |
      |          |         _|_
      |       ___|___     __|__
  ____|____  ____|____  ____|____ (A -> B)

(3.1) |          |          |
      |          |          |
     _|_      ___|___     __|__
  ____|____  ____|____  ____|____ (C -> A)

(3.2) |          |          |
      |        __|__        |
     _|_      ___|___       |
  ____|____  ____|____  ____|____ (C -> B)

(3.3) |         _|_         |
      |        __|__        |
      |       ___|___       |
  ____|____  ____|____  ____|____ (A -> B)

Le problème des 3 anneaux a été divisé en 2 problèmes de 2 anneaux (1.x et 3.x).

Answer 3

Une bonne explication de l'implémentation récursive de Hanoi se trouve à l'adresse suivante http://www.cs.cmu.edu/~cburch/survey/recurse/hanoiimpl.html .

En résumé, si vous voulez déplacer la plaque inférieure du bâton A vers le bâton B, vous devez d'abord déplacer toutes les plaques plus petites situées au-dessus de A vers C. Le deuxième appel récursif consiste alors à déplacer les plaques que vous avez déplacées vers C vers B après que votre cas de base ait déplacé la grande plaque unique de A vers B.

Answer 4

Je reconnais que celui-ci n'est pas immédiat quand on le regarde pour la première fois, mais il est assez simple quand on s'y met.

Cas de base : votre tour est de taille 1. Vous pouvez donc le faire en un seul mouvement, de la source directement à la destination.

Cas récursif : votre tour est de taille n > 1. Vous déplacez donc la tour supérieure de taille n-1 sur un piquet supplémentaire (by), vous déplacez la "tour" inférieure de taille 1 sur le piquet de destination, et vous déplacez la tour supérieure de by à dest.

Ainsi, dans un cas simple, vous avez une tour de hauteur 2 :

 _|_    |     |
__|__   |     |
===== ===== =====

Première étape : déplacez la tour supérieure de 2-1 (=1) vers la cheville supplémentaire (celle du milieu, par exemple).

  |     |     |
__|__  _|_    |
===== ===== =====

Suivant : déplacez le disque inférieur vers la destination :

  |     |     |
  |    _|_  __|__
===== ===== =====

Et enfin, déplacer la tour supérieure de (2-1)=1 vers la destination.

  |     |    _|_
  |     |   __|__
===== ===== =====

Si vous y réfléchissez, même si la tour était de 3 ou plus, il y aura toujours un piquet supplémentaire vide, ou un piquet avec tous les disques les plus grands, que la récursion pourra utiliser pour échanger les tours.

Answer 5

Supposons que nous voulions déplacer un disque de A à C en passant par B alors :

1. déplacer un disque plus petit vers B.
2. déplacer un autre disque vers C.
3. déplacer B vers C.
4. se déplacer de A à B.
5. déplacer tout de C à A.

Si vous répétez toutes les étapes ci-dessus, le disque sera transféré.