Tour de Hanoi: algorithme récursif

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

Pour déplacer n disques de la cheville A à la cheville C:

1. déplacer n − 1 disques de A à B. Cela laisse le disque #n seul sur le pion A
2. déplacer le disque n de A à C
3. déplacer n-1 disques de B vers C pour qu’ils soient assis sur le disque #n

Il est évident que vous devez d’abord supprimer n -1 disques pour accéder au n- ième. Et que vous devez les déplacer d’abord vers un autre piquet que là où vous voulez que la tour complète apparaisse.

Outre le nombre de disques, le code de votre article comporte trois arguments: un code source , un sharepoint destination et un sharepoint connexion temporaire sur lequel les disques peuvent être stockés (où chaque disque de taille n – 1 correspond).

La récursivité se produit en fait deux fois, une fois avant l’ writeln , une fois après. Celui qui précède le writeln déplacera n – 1 disques sur le lien temporaire, en utilisant le code de destination comme stockage temporaire (les arguments de l’appel récursif sont dans un ordre différent). Après cela, le disque restant sera déplacé vers le pion de destination et la seconde récursivité comstackra ensuite le déplacement de la tour entière, en déplaçant la tour n -1 du piquet temp vers le pion de destination, au-dessus du disque n.

il y a un an, j’ai eu cours de functional programming et dessiner cette illustration pour l’algorithme. J’espère que cela aide!

 (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 à 2 anneaux (1.x et 3.x)

Il y a une bonne explication de l’implémentation récursive de Hanoi à http://www.cs.cmu.edu/~cburch/survey/recurse/hanoiimpl.html .

En résumé, si vous voulez déplacer la plaque du bas du bâton A au bâton B, vous devez d’abord déplacer toutes les petites plaques de A à C. Le deuxième appel récursif est alors de déplacer les plaques que vous avez déplacées vers C de nouveau sur B après que votre cas de base ait déplacé la grande plaque unique de A à B.

Je suis d’accord que celui-ci n’est pas immédiat lorsque vous le regardez pour la première fois, mais c’est assez simple lorsque vous y arrivez.

Cas de base: votre tour est de taille 1. Vous pouvez donc le faire d’un coup, 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 (par), déplacez la “tour” inférieure de taille 1 vers le piquet de destination et déplacez la tour supérieure de par à destination.

Donc, avec un cas simple, vous avez une tour de hauteur 2:

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

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

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

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

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

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

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

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

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

1. déplacer un disque plus petit vers B.
2. déplacer un autre disque vers C.
3. déplacez B vers C.
4. passer 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é.

Je ressens la douleur!

Bien qu’il s’agisse d’un ancien message, je pense que ce qu’il faut vraiment comprendre, ce n’est pas l’approche «déplacer cela vers cela» mais que la réponse implique l’utilisation de l’effet secondaire de la récursivité.

Une aide inestimable pour moi a été le “Petit Schemer” qui apprend à penser et à écrire des fonctions récursives.

Cependant, cela enseigne au lecteur à utiliser les résultats du résultat renvoyé dans le prochain appel récursif.

Dans la tour de Hanoi, la réponse n’est pas dans le résultat renvoyé en soi, mais dans l’observation du résultat renvoyé.

La magie se produit lors du réarrangement successif des parameters de la fonction.

Oui, le problème est vraiment en trois parties:

• déplacer une tour plus petite à la cheville de rechange
• déplacer le dernier disque vers le pion de destination
• déplacer la tour restante sur le piquet de rechange vers le piquet de destination.

Dans le schéma:

 (define (th nabc) (if (zero? n) 'done (begin (th (- n 1) acb) (display (list ac)) (newline) (th (- n 1) bac)))) (th 5 'source 'spare 'destination) 

Cependant, c’est l’affichage des parameters de la fonction qui est la solution au problème et la compréhension cruciale de la structure en double arbre des appels.

La solution transmet également le pouvoir de la proof by induction et une lueur chaleureuse à tous les programmeurs qui ont lutté avec les structures de contrôle conventionnelles.

Incidemment, résoudre le problème à la main est tout à fait satisfaisant.

• compter le nombre de disques
• si même, déplacez le premier disque sur la cheville de rechange, effectuez le prochain mouvement légal (sans impliquer le disque supérieur). Puis déplacez le disque supérieur vers le pion de destination, effectuez le prochain mouvement légal (nittd). Puis déplacez le disque supérieur vers le pion source, effectuez le prochain mouvement légal (nittd) …
• s’il est étrange, déplacez le premier disque vers le pion de destination, effectuez le prochain mouvement légal (sans impliquer le disque supérieur). Ensuite, déplacez le disque supérieur vers le pion de rechange, effectuez le mouvement légal suivant (nittd). Puis déplacez le disque supérieur vers le pion source, effectuez le prochain mouvement légal (nittd) …

Pour ce faire, maintenez toujours le disque supérieur avec la même main et déplacez toujours cette main dans la même direction.

Le nombre final de mouvements pour n disques est de 2^n - 1 le move n disc to destination est à mi-chemin du processus.

Enfin, il est amusant de voir comment expliquer un problème à un collègue, à votre femme / mari ou même au chien (même s’ils n’écoutent pas) peut cimenter l’illumination.

Après avoir lu toutes ces explications, je pensais que je devais utiliser la méthode utilisée par mon professeur pour expliquer la solution récursive des Tours de Hanoi. Voici encore l’algorithme avec n représentant le nombre d’anneaux, et A, B, C représentant les pions. Le premier paramètre de la fonction est le nombre de sonneries, le deuxième paramètre représente le peg de la source, le troisième le pion de destination et le quasortingème le pion de réserve.

 procedure Hanoi(n, A, B, C); if n == 1 move ring n from peg A to peg B else Hanoi(n-1, A, C, B); move ring n-1 from A to C Hanoi(n-1, C, B, A); end; 

On m’a enseigné à l’école supérieure pour ne jamais avoir honte de penser petit. Alors, regardons cet algorithme pour n = 5. La question à se poser en premier est si je veux déplacer le 5ème anneau de A à B, où sont les 4 autres anneaux? Si le 5ème anneau occupe le pion A et que l’on veut le déplacer sur le pion B, alors les 4 autres anneaux ne peuvent être que sur le pion C. Dans l’algorithme au-dessus de la fonction, Hanoi (n-1, A, C, B) déplacez tous ces 4 autres anneaux sur C, donc l’anneau 5 pourra se déplacer de A à B. En suivant cet algorithme, nous regardons n = 4. Si l’anneau 4 sera déplacé de A à C, où sont les anneaux 3 et plus petit? Ils ne peuvent être que sur peg B. Ensuite, pour n = 3, si l’anneau 3 sera déplacé de A à B, où sont les anneaux 2 et 1? Sur la cheville C bien sûr. Si vous continuez à suivre ce modèle, vous pouvez visualiser ce que fait l’algorithme récursif. Cette approche diffère de l’approche du novice en ce qu’elle examine le premier disque en premier et le premier en dernier.

Considérez-le comme une stack dont le diamètre des disques est représenté par des entiers (4,3,2,1). Le premier appel de récursivité sera appelé 3 fois et remplira ainsi la stack d’exécution comme suit

1. premier appel: 1. Deuxième appel: 2,1. et troisième appel: 3,2,1.

À la fin de la première récursivité, le contenu de la stack d’exécution est envoyé au pôle central du plus grand diamètre au plus petit (premier entré, dernier sorti). Ensuite, le disque de diamètre 4 est déplacé vers la destination.

Le deuxième appel de récursivité est le même que le premier, à l’exception du déplacement des éléments du pôle central vers la destination.

C’est simple. Supposons que vous voulez passer de A à C

s’il n’y a qu’un seul disque, déplacez-le simplement.

S’il y a plus d’un disque, faites

• déplacer tous les disques (n-1 disques), sauf celui du bas de A à B
• déplacer le disque inférieur de A à C
• déplacer les n-1 disques du premier pas de A à C

Gardez à l’esprit que lors du déplacement des disques n-1, le nième ne sera pas un problème (une fois plus gros que tous les autres)

Notez que le déplacement des disques n-1 revient sur le même problème, jusqu’à ce que n-1 = 1, auquel cas vous serez sur le premier si (où vous devez simplement le déplacer).

La réponse à la question, comment le programme sait-il, qui est même “src” à “aux”, et impaire est “src” à “dst” pour le coup d’ouverture réside dans le programme. Si vous décomposez le coup de poing avec 4 disques, alors ceci ressemble à ceci:

 hanoi(4, "src", "aux", "dst"); if (disc > 0) { hanoi(3, 'src', 'dst', 'aux'); if (disc > 0) { hanoi(2, 'src', 'aux', 'dst'); if (disc > 0) { hanoi(1, 'src', 'dst', 'aux'); if (disc > 0) { hanoi(0, 'src', 'aux', 'dst'); END document.writeln("Move disc" + 1 + "from" + Src + "to" + Aux); hanoi(0, 'aux', 'src', 'dst'); END } 

aussi le premier coup avec 4 disques (pair) va de Src à Aux.

Comme l’ont suggéré certains de nos amis, j’ai retiré les deux réponses précédentes et je consolide ici.

Cela vous donne une compréhension claire.

Qu’est-ce que l’algorithme général est ….

Algorithme:

 solve(n,s,i,d) //solve n discs from s to d, s-source i-intermediate d-destination { if(n==0)return; solve(n-1,s,d,i); // solve n-1 discs from s to i Note:recursive call, not just move move from s to d; // after moving n-1 discs from s to d, a left disc in s is moved to d solve(n-1,i,s,d); // we have left n-1 disc in 'i', so bringing it to from i to d (recursive call) } 

voici l’exemple de travail Cliquez ici

 public static void hanoi(int number, Ssortingng source, Ssortingng aux, Ssortingng dest) { if (number == 1) { System.out.println(source + " - > "+dest); } else{ hanoi(number -1, source, dest, aux); hanoi(1, source, aux, dest); hanoi(number -1, aux, source, dest); } } 

 void TOH(int n, int a, int b){ /*Assuming a as source stack numbered as 1, b as spare stack numbered as 2 and c as target stack numbered as 3. So once we know values of a and b, we can determine c as there sum is a constant number (3+2+1=)6. */ int c = 6-ab; if(n==1){ cout<<"Move from "<