Tour de Hanoi: Algorithme Récursif
Bien que je n'ai aucun problème que ce soit la compréhension de la récursivité, je n'arrive pas à envelopper ma tête autour de la solution récursive de la Tour de Hanoi problème. Voici le code de Wikipédia:
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 rompre le problème en petits morceaux jusqu'à ce que vous êtes capable de déplacer un seul disque. Cependant, je ne peux pas comprendre comment les deux appels récursifs dans le non-cas de base de travail ensemble. Peut-être que quelqu'un peut m'aider? Merci.
- Ce code pourrait être améliorée par la vérification pour n=0 et ne rien faire dans ce cas, pour éviter la duplication de la déplacer.
- Cela peut vous aider: learneroo.com/modules/71/nodes/402
- J'ai écrit un billet de blog sur la récursivité lui-même. Il va dans une extrême profondeur et, très honnêtement, il prend un certain temps à comprendre mais une fois que vous le visualisez, il fait tellement plus de sens. Sérieusement, vous épargner du temps et de vérifier cela: dima.de/blog/?p=29
- En fait l'idée de base est que si nous voulons résoudre le problème pour N disques alors nous pouvons utiliser de nouveau le problème avec les N-1 disques. Le cas de Base est lorsque N = 1. J'ai essayé de l'expliquer dans mon blog à l'aide du code Java. krishnalearnings.blogspot.dans/2015/06/...
- Vous pouvez essayer de créer une visualisation comme ceci: thewalnut.io/visualiseur/visualiser/1322/342 pour voir si elle aide à comprendre...
Vous devez vous connecter pour publier un commentaire.
En fait, la section où vous avez pris ce code propose une explication ainsi:
Il est assez clair que vous devez d'abord enlever n − 1 disques pour obtenir l'accès à la ne. Et que vous devrez les déplacer à un autre peg de ce que vous voulez de la tour complet à apparaître.
Le code dans votre post a trois arguments, outre le nombre de disques: Un source peg, un destination peg et un temporaire peg sur les disques peuvent être stockés dans l'entre (où chaque disque avec la taille n − 1 s'adapte).
La récursivité qui se passe réellement deux fois, là, une fois avant le
writeln
, la fois d'après. Celle d'avant lawriteln
va se déplacer n − 1 disques sur le temporaire peg, à l'aide de la destination peg pour le stockage temporaire (les arguments dans l'appel récursif sont dans un ordre différent). Après cela, le reste du disque seront déplacés vers la destination de peg et après la deuxième récursivité compeltes le déplacement de l'ensemble de la tour, par le déplacement de la n − 1 tour de la temp de peg à la destination de peg, au-dessus du disque n.il y a une année j'ai eu j'ai de la programmation fonctionnelle cours et dessiner cette illustration de l'algorithme.
espérons que cela aide!
Les 3 anneaux problème a été découpé à 2 de 2 anneaux de problème (1.x et 3.x)
Il y a une bonne explication de la récursivité Hanoi mise en œuvre au http://www.cs.cmu.edu/~cburch/survey/recurse/hanoiimpl.html.
Résumé, si vous souhaitez déplacer la plaque de fond de bâton, Un bâton à B, vous devez d'abord déplacer toutes les petites plaques sur le dessus de il de A à C. Le deuxième appel récursif est alors de déplacer les plaques, vous avez déménagé à la C à l'arrière sur B après votre base de cas déplacé la seule grande plaque allant de A à B.
Je suis d'accord ce n'est pas immédiate quand vous regardez d'abord, mais il est assez simple lorsque vous descendez à elle.
Cas de Base: votre tour de taille 1. De sorte que vous pouvez le faire en un seul coup, à partir de la source directement dans dest.
Récursive cas: votre tour de taille n > 1. Si vous déplacez le sommet de la tour de taille n-1 pour un supplément de peg (par), déplacez le bas de la "tour" de la taille 1 à la destination de peg, et de déplacer le sommet de la tour de par de dest.
Donc, avec un cas simple, vous avez un tour de taille 2:
Première étape: déplacer le sommet de la tour de 2-1 (=1) pour l'ancrage extra (celui du milieu, permet de dire).
Suivante: déplacer le disque inférieur de la destination:
Et enfin, déplacez le sommet de la tour de (2-1)=1 pour la destination.
Si vous pensez à ce sujet, même si la tour avait 3 ou plus, il y aura toujours un vide supplémentaire peg, ou un peg avec tous les grands disques, de la récursion à utiliser lors de la permutation des tours autour de.
Supposons que l'on souhaite déplacer un disque de A à C en passant par B, alors:
Si vous répétez toutes les étapes ci-dessus, le disque de transfert.
Je sens la douleur!
Bien que c'est un vieux post, je pense que ce que l'on a vraiment besoin de comprendre, n'est pas le "déplacement de cette de cette" approche, mais que la réponse implique l'utilisation de l'effet de bord de la récursivité.
Une aide précieuse pour moi, c'était la "Le Petit Intrigant", qui apprend à penser et à écrire des fonctions récursives.
Toutefois, cela apprend au lecteur à utiliser les résultats de l'renvoyé de résultat dans le prochain appel récursif.
Dans la Tour de Hanoi, la réponse n'est pas dans le résultat retourné en soi, mais dans l'observation du résultat retourné.
La magie se produit dans l'successives rearrangment des paramètres de la fonction.
Oui, le problème est vraiment en trois parties:
Dans Le Schéma:
Cependant, c'est l'affichage des paramètres de la fonction qui est la solution du problème, et surtout la compréhension de la double arbre comme la structure de la demande.
La solution permet de transmettre la puissance de
proof by induction
et un lueur chaude à tous les programmeurs qui ont lutté avec les classiques des structures de contrôle.Incidemment, à résoudre le problème en main est assez satisfaisant.
Mieux faire en tenant toujours le disque supérieur avec la même main et toujours en mouvement qui part dans la même direction.
Le nombre final de déplacements pour
n
disques est2^n - 1
lamove n disc to destination
est à mi-chemin à travers le processus.Enfin, il est drôle de voir comment expliquant un problème à un collègue, à votre femme/mari ou même le chien (même si ce qu'ils ne les écoute pas) peut ciment de l'illumination.
Après la lecture de toutes ces explications, je pensais que je serais de peser dans la méthode de mon professeur utilisé pour expliquer les Tours de Hanoi solution récursive. Voici l'algorithme de nouveau avec n représentant le nombre d'anneaux, et A, B, C représentent les chevilles. Le premier paramètre de la fonction est le nombre d'anneaux, second paramètre représente la source de peg, la troisième est la destination de peg, et la quatrième est la pièce de rechange peg.
J'ai appris à l'école d'études supérieures de ne jamais avoir honte de penser petit. Alors, regardons cet algorithme pour n = 5. La question à se poser, la première est si je veux déplacer la 5ème anneau de A à B, où sont les autres 4 anneaux? Si la 5ème anneau occupe Un peg et nous voulons aller à peg B, puis de l'autre 4 anneaux ne peuvent être à la peg C. Dans l'algorithme ci-dessus la fonction Hanoi (n-1, A, C, B) est d'essayer de déplacer tous ces 4 autres anneaux d'ancrage C, de sorte que l'anneau 5 sera capable de se déplacer d'Un point a à B. Suite à cet algorithme, nous regardons n = 4. Si l'anneau 4 sera déplacée de A à C, où sont des anneaux 3 et plus petits? Ils ne peuvent être à la peg B. Ensuite, pour n = 3, si la bague 3 est déplacé d'Un point a à B, où sont des anneaux 2 et 1? Sur peg C bien sûr. Si vous continuez à suivre ce modèle, vous pouvez le visualiser ce que l'algorithme récursif est en train de faire. Cette approche diffère de la novice de l'approche qu'il regarde le dernier disque de la première et le premier disque de la dernière.
Penser à cela comme une pile avec les disques de diamètre être représentées par des nombres entiers (4,3,2,1)
La première récursivité appel sera appelé 3 fois et ainsi de remplissage de la pile comme suit
Après la première récursivité se termine, le contenu de la pile est sorti au milieu pôle de plus grand diamètre au plus petit (de la première à la dernière). Ensuite, le disque avec un diamètre de 4 est déplacé vers la destination.
La deuxième récursivité appel est le même que le premier, à l'exception de déplacer les éléments à partir du milieu pôle de destination.
Le premier appel récursif se déplace toutes les pièces à l'exception de la plus grande à partir de la source en utilisant dest que la pile auxiliaire. Lorsque tous les morceaux, sauf les plus grands se trouvent sur par et le plus grand, est gratuit. Maintenant, vous pouvez déplacer le plus gros à destination et en utiliser un autre appel récursif pour déplacer toutes les pièces de par de dest.
Les appels récursifs ne savez rien à propos de la plus grande pièce (c'est à dire qu'ils vont l'ignorer), mais c'est ok parce que les appels récursifs ne traitons qu'avec les pièces qui sont plus petits et donc peut être déplacé dans et hors le plus gros morceau librement.
C'est simple. Supposons que vous souhaitez déplacer d'Un point a à C
si il n'y a qu'un seul disque, juste le déplacer.
Si il n'y a plus d'un disque, ne
Gardez à l'esprit que, lors du déplacement de la n-1 disques, le nième ne sera pas un problème du tout (une fois qu'il est plus grand que tous les autres)
Remarque que le fait de déplacer n-1 disques réapparaît sur le même problème à nouveau, jusqu'à ce que n-1 = 1, auquel cas, vous allez être le premier si (où vous devez simplement la déplacer).
La réponse pour la question, comment le programme peut-il savoir, que même est "src" "aux", et de l'impair est "src" à "heure d'été" pour l'ouverture réside dans le programme. Si vous décomposez le poing se déplacer avec 4 disques, alors cela ressemble à ceci:
aussi le premier mouvement avec 4 disque(même) va de la Src pour Aux.
Comme certains de nos amis ont suggéré, j'ai enlevé deux précédentes réponses et je les regrouper ici.
Cela vous donne une claire compréhension.
Ce que l'algorithme général est....
Algorithme:
ici est l'exemple Cliquez ici
Il y a trois tours, à savoir la source de tour de, tour de destination et d'assistance de la tour. La source de la tour dispose de tous les disques et votre objectif est de déplacer tous les disques à la destination de la tour et assurez-vous que vous ne mettez jamais un plus grand disque sur un disque plus petit. Nous pouvons résoudre ce problème en utilisant la récursivité dans les étapes ci-dessous:
Nous avons n nombre de disques sur la source du tour
Cas de Base: n=1
Si il y a un seul disque dans la source de la tour, le déplacer à destination de la tour.
Récursive cas: n >1
tour
la tour, à l'aide de la source de la tour comme une aide.
Code Source en Java:
Comme une CS d'étudiant, vous pourriez avoir entendu parler induction Mathématique.
La solution récursive de la Tour de Hanoi fonctionne de façon analogue seule autre partie est vraiment pas perdu avec B et C ont le plein tour se termine.
Dans le simple sens, l'idée est de remplir un tour parmi les trois tours du même ordre de disques, comme le présent, sans un plus grand disque de chevauchement d'un petit disque à tout moment au cours de la procédure.
Laisser 'A' , 'B' et 'C' de trois tours. 'A' sera le tour contenant 'n' disques initialement. 'B' peut être utilisé comme intermédiaire de la tour et " C " est la cible de la tour.
L'algo est comme suit:
Le code est comme suit en java:
public class TowerOfHanoi {
}
Voici l'explication. Regardez l'image ->
En appelant
Movetower(3,a,b,c)
, vous avez l'intention de déplacer tous les 3 disques de la tourA
à tourB
. Si la séquence d'appels sont ->Espère que cela aide 🙂
Pour L'Animation : https://www.cs.cmu.edu/~cburch/survey/recurse/hanoiex.html
Voici ma solution code à Tours de Hanoï problème en utilisant la récursivité avec golang. `package principal
Ce python3 exemple utilise une solution récursive:
De sortie:
Mais bien sûr, le moyen le plus efficace pour savoir combien de coups est de réaliser que les réponses sont toujours de 1 à moins de 2^n. Donc, la solution mathématique est de 2^n - 1
Tower (N,source,aux.dest):
déplacer N-1 disques de peg source de peg aux
déplacer N-1 disques de peg auxiliaire peg dest
/**
*
*/
package com.test.la récursivité;
/**
* @author kamals1986 L'algorithme Récursif pour la Tour de Hanoi Problème de La
* algorithme grandit en puissance(2,n).
*/
public class TowerOfHanoi {
}
J'essaie d'obtenir la récursivité trop.
J'ai trouvé un moyen, je pense,
je pense c'est comme une chaîne d'étapes(de l'étape n'est pas constant, il peut changer en fonction du nœud précédent)
Je dois trouver 2 choses:
exemple
factorielle
1,2,6,24,120 ......... ou
1,2*(1),3*(2*1),4*(3*2*1,5*(4*3*2*1)
étape=multiple par dernier nœud
après l'étape ce que j'ai besoin de faire le nœud suivant,abrégé 1
ok
je espère que cette aide,il suffit de penser à propos de 2 thniks,pas comment aller d'un nœud à un nœud,mais le nœud-->étape-->nœud
nœud-->étape est le corps de la fonction
étape-->nœud est les arguments de la fonction
bye:) j'espère que j'ai aidé