wake-up-neo.com

Turm von Hanoi: Rekursiver Algorithmus

Obwohl ich keinerlei Probleme damit habe, die Rekursion zu verstehen, kann ich mich nicht mit der rekursiven Lösung des Tower of Hanoi-Problems beschäftigen. Hier ist der Code aus 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;

Ich verstehe den Basisfall und das Konzept, das Problem in kleinere Teile zu zerlegen, bis Sie eine einzelne Festplatte verschieben können. Ich kann jedoch nicht herausfinden, wie die beiden rekursiven Aufrufe im Nicht-Basisfall zusammenarbeiten. Vielleicht kann mir jemand weiterhelfen? Vielen Dank.

62
titaniumdecoy

Eigentlich bietet der Abschnitt, von dem Sie den Code genommen haben auch eine Erklärung:

So verschieben Sie n Scheiben von Stift A zu Stift C:

  1. bewegen Sie n-1 Scheiben von A nach B. Dadurch bleibt die Scheibe #n auf dem Stift A 
  2. verschieben Sie die Disc #n von A nach C 
  3. bewegen Sie n-1 Scheiben von B nach C, damit sie auf Scheibe #n sitzen

Es ist ziemlich klar, dass Sie zuerst n - 1 Discs entfernen müssen, um Zugriff auf die n -te zu erhalten. Und dass Sie sie zuerst auf einen anderen Stift verschieben müssen, als dort, wo der volle Turm erscheinen soll.

Der Code in Ihrem Beitrag enthält neben der Anzahl der Discs drei Argumente: einen source -, einen destination - und einen temporären - Peg, auf dem die Discs (wo jede Disc gespeichert werden kann) gespeichert werden mit Größe n - 1 passt).

Die Rekursion findet tatsächlich zweimal statt, einmal vor der writeln, einmal danach. Die eine vor der Variablen writeln wird n - 1-Disks auf den temporären Peg verschieben, wobei der Ziel-Peg als temporärer Speicher verwendet wird (die Argumente im rekursiven Aufruf sind in unterschiedlicher Reihenfolge). Danach wird die verbleibende Scheibe zum Zielhalter bewegt, und danach wird die Bewegung des gesamten Turms durch die zweite Rekursion durchgeführt, indem der Turm n - 1 vom Temp-Stift zum Zielstift über dem Teller bewegt wird n.

46
Joey

vor einem Jahr hatte ich einen funktionalen Programmierkurs und zeichne diese Illustration für den Algorithmus. Ich hoffe es hilft!

(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)

Das 3-Ringe-Problem wurde auf 2 2-Ringe-Problem (1.x und 3.x) aufgeteilt.

31
f0b0s

Es gibt eine gute Erklärung für die rekursive Implementierung von Hanoi unter http://www.cs.cmu.edu/~cburch/survey/recurse/hanoiimpl.html .

Wenn Sie die untere Platte von Stick A nach Stick B verschieben möchten, müssen Sie zunächst alle kleineren darüber liegenden Platten von A nach C bewegen. Der zweite rekursive Aufruf besteht darin, die von Ihnen nach C verschobenen Platten zu verschieben zurück auf B, nachdem Ihr Basisgehäuse die einzelne große Platte von A nach B verschoben hat.

14
matthock

Ich stimme zu, dass dies nicht sofort eintritt, wenn Sie es zum ersten Mal betrachten, aber es ist ziemlich einfach, wenn Sie es anfangen.

Basisfall: Ihr Turm hat die Größe 1. Sie können es also in einem Zug tun, von der Quelle direkt zum Ziel.

Rekursiver Fall: Ihr Turm hat die Größe n> 1. Bewegen Sie den oberen Turm der Größe n-1 auf einen zusätzlichen Stift (durch), verschieben Sie den unteren "Turm" der Größe 1 zum Zielstift und verschieben Sie den oberen Turm von by bis dest.

In einem einfachen Fall haben Sie einen Turm der Höhe 2:

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

Erster Schritt: Bewegen Sie den oberen Turm von 2-1 (= 1) auf den zusätzlichen Stift (den mittleren, sagen wir mal).

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

Weiter: Verschieben Sie die unterste Disc an den Zielort:

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

Bewegen Sie schließlich den obersten Turm von (2-1) = 1 zum Ziel.

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

Wenn Sie darüber nachdenken, auch wenn der Turm 3 oder mehr gewesen wäre, wird immer ein leerer zusätzlicher Stift oder ein Stift mit allen größeren Scheiben für die Rekursion verwendet, wenn Sie die Türme austauschen.

13
Sean

Angenommen, wir möchten eine CD von A nach C durch B verschieben, dann:

  1. verschieben Sie eine kleinere Scheibe nach B.
  2. schieben Sie eine andere Disc nach C.
  3. bewege B nach C.
  4. von A nach B wechseln.
  5. verschiebe alles von C nach A.

Wenn Sie alle obigen Schritte wiederholen, wird die Disc übertragen.

Stellen Sie sich dies als einen Stapel vor, bei dem der Scheibendurchmesser durch ganze Zahlen (4,3,2,1) .__ dargestellt wird. Der erste Rekursionsaufruf wird dreimal aufgerufen und füllt den Laufzeitstapel daher wie folgt

  1. erster Anruf: 1. zweiter Anruf: 2,1. und dritter Anruf: 3,2,1.

Nachdem die erste Rekursion beendet ist, wird der Inhalt des Laufzeitstapels vom größten Durchmesser zum kleinsten (zuerst in letzter Ausgabe) auf den mittleren Pol verschoben. Als nächstes wird die Platte mit dem Durchmesser 4 zum Ziel verschoben.

Der zweite Rekursionsaufruf ist derselbe wie der erste, mit der Ausnahme, dass die Elemente vom mittleren Pol zum Ziel verschoben werden. 

2
Ahmad

Ich spüre den Schmerz! 

Obwohl dies ein alter Beitrag ist, denke ich, ist das, was man wirklich verstehen muss, nicht der "Move this to" -Ansatz, sondern die Antwort beinhaltet den Nebeneffekt der Rekursion.

Eine unschätzbare Hilfe für mich war der "Der kleine Schemer", der das Rekursive Denken und Schreiben lehrt. 

Dies lehrt den Leser jedoch, die Ergebnisse des zurückgegebenen Ergebnisses beim nächsten rekursiven Aufruf zu verwenden. 

Im Turm von Hanoi liegt die Antwort nicht im zurückgegebenen Ergebnis an sich, sondern in der Beobachtung des zurückgegebenen Ergebnisses. 

Das magic tritt in der nachfolgenden Umstellung der Funktionsparameter auf.

Ja, das Problem besteht wirklich aus drei Teilen:

  • bewegen eines kleineren Turms zum Ersatzstift
  • bewegen der letzten Disc auf den Zielbolzen
  • bewegen des verbleibenden Turms auf dem Ersatzzapfen zum Zielzapfen.

In Schema:

(define (th n a b c)
    (if (zero? n) 'done
        (begin
           (th (- n 1) a c b)
           (display (list a c))
           (newline)
           (th (- n 1) b a c))))
(th 5 'source 'spare 'destination)

Es ist jedoch die Anzeige der Funktionsparameter, die die Lösung des Problems ist, und die doppelstrukturartige Struktur der Aufrufe entscheidend zu verstehen.

Die Lösung vermittelt auch die Kraft von proof by induction und ein warmes Glowan alle Programmierer, die mit herkömmlichen Kontrollstrukturen gerungen haben.

Übrigens ist es durchaus befriedigend, das Problem von Hand zu lösen.

  • zählen Sie die Anzahl der Scheiben
  • wenn Sie gerade sind, bewegen Sie die erste Disc auf den Ersatzstift. Führen Sie die nächste legale Bewegung aus (ohne die obere Disc). Bewegen Sie dann die obere Scheibe zum Zielhalter, und machen Sie den nächsten legalen Schritt (nittd). Dann schieben Sie die obere Scheibe zum Ursprungsstift, machen Sie den nächsten legalen Schritt (nittd) ...
  • wenn Sie ungerade sind, verschieben Sie die erste Disc zum Zielbolzen und führen Sie die nächste legale Bewegung aus (ohne die obere Disc). Bewegen Sie dann die obere Scheibe zum Ersatzstift, und machen Sie den nächsten legalen Schritt (nittd). Dann schieben Sie die obere Scheibe zum Ursprungsstift, machen Sie den nächsten legalen Schritt (nittd) ...

Am besten halten Sie die obere Scheibe immer mit derselben Hand und bewegen diese Hand immer in dieselbe Richtung.

Die endgültige Anzahl der Verschiebungen für n-Discs ist 2^n - 1, der move n disc to destination ist zur Hälfte des Vorgangs.

Schließlich ist es komisch, wie das Erklären ein Problem für einen Kollegen, Ihre Frau/Ihren Ehemann oder sogar den Hund (selbst wenn sie nicht zuhören) die Aufklärung festigen kann. 

2
potong

Nachdem ich all diese Erklärungen gelesen hatte, dachte ich, ich würde mich mit der Methode abfinden, mit der mein Professor die rekursive Lösung von Towers of Hanoi erklärte. Hier ist der Algorithmus erneut mit n , das die Anzahl der Ringe darstellt, und A, B, C, die die Stifte darstellen. Der erste Parameter der Funktion ist die Anzahl der Klingelzeichen, der zweite Parameter stellt den Quellstift dar, der dritte ist der Zielstift und der vierte ist der Ersatzstift.

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;

Ich wurde in der Graduiertenschule unterrichtet, um mich nie zu schämen, klein zu denken. Schauen wir uns diesen Algorithmus für n = 5 an. Die Frage, die Sie sich zuerst stellen sollten, ist wenn ich den 5. Ring von A nach B verschieben möchte, wo sind dann die anderen 4 Ringe? Wenn der 5. Ring den Stift A belegt und wir ihn auf den Stift B verschieben möchten, können die anderen 4 Ringe nur auf dem Stift C stehen. Im obigen Algorithmus ist die Funktion Hanoi (n-1, A, C, B ) versucht, alle 4 anderen Ringe auf den Stift C zu verschieben, sodass Ring 5 von A nach B wechseln kann. Nach diesem Algorithmus betrachten wir n = 4. Wenn Ring 4 von A nach C verschoben wird , wo sind Ringe 3 und kleiner? Sie können sich nur auf Stift B befinden. Als nächstes wird für n = 3, wenn Ring 3 von A nach B verschoben wird, wo sind dann die Ringe 2 und 1? Natürlich auf Stift C. Wenn Sie diesem Muster weiterhin folgen, können Sie visualisieren, was der rekursive Algorithmus tut. Dieser Ansatz unterscheidet sich vom Ansatz des Neulings insofern, als er die letzte und die erste zuerst betrachtet.

2
MNRC
public static void hanoi(int number, String source, String aux, String 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);
    }
}
1
Rafael Amsili

Es ist einfach. Angenommen, Sie möchten von A nach C wechseln

wenn es nur eine Platte gibt, verschieben Sie sie einfach.

Wenn es mehr als eine Platte gibt, tun Sie dies

  • bewegen Sie alle Festplatten (n-1-Festplatten) mit Ausnahme der untersten von A nach B
  • bewegen Sie die untere Scheibe von A nach C
  • bewegen Sie die n-1-Datenträger vom ersten Schritt von A nach C

Denken Sie daran, dass die n-1-Disk beim Verschieben der n-1-Festplatten überhaupt kein Problem darstellt (sobald sie größer ist als alle anderen).

Beachten Sie, dass das Verschieben der n-1-Disketten mit demselben Problem erneut auftritt, bis n-1 = 1 ist. In diesem Fall befinden Sie sich beim ersten (wenn Sie es gerade verschieben).

1
Samuel Carrijo

Wie einige unserer Freunde vorgeschlagen haben, habe ich die vorherigen beiden Antworten entfernt und hier konsolidieren.

Dies gibt Ihnen ein klares Verständnis.

Was ist der allgemeine Algorithmus?.

Algorithmus: 

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)
}

hier ist das Arbeitsbeispiel hier klicken

1
Vivek MVK

Die Antwort auf die Frage, woher das Programm weiß, dass "src" bis "aux" und ungerade "src" bis "dst" für den Eröffnungszug ist, liegt im Programm. Wenn Sie die Faustbewegung mit 4 Scheiben abbauen, sieht das so aus:

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
                        }

auch der erste Zug mit 4 Discs (gerade) geht von Src nach Aux. 

1
dspkwa
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-a-b;
if(n==1){
    cout<<"Move from "<<a<<" to "<<b<<"\n";
}
else{
    // Move n-1 disks from 1st to 2nd stack. As we are not allowed to move more than one disks at a time, we do it by recursion. Breaking the problem into a simpler problem.
    TOH(n-1, a, c);
    // Move the last alone disk from 1st to 3rd stack.
    TOH(1, a, b);
    // Put n-1 disks from 2nd to 3rd stack. As we are not allowed to move more than one disks at a time, we do it by recursion. Breaking the problem into a simpler problem.        
    TOH(n-1, c, b);
}
}
int main() {

TOH(2, 1, 3);
cout<<"FINISHED                        \n";
TOH(3, 1, 3);
cout<<"FINISHED                        \n";
TOH(4, 1, 3);
return 0;
}
1
Aditya Raj

Es gibt drei Türme, nämlich Quellturm, Zielturm und Helmturm. Der Quellturm enthält alle Festplatten. Ihr Ziel ist es, alle Festplatten zum Zielturm zu verschieben und dabei sicherzustellen, dass Sie niemals eine größere Festplatte auf eine kleinere Festplatte legen. Wir können dieses Problem durch Rekursion in den folgenden Schritten lösen:

Wir haben n Anzahl der Festplatten am Quellturm

Basisfall: n = 1 Wenn sich im Quellturm nur eine Platte befindet, verschieben Sie sie in den Zielturm. 

Rekursiver Fall: n> 1  

  • Bewegen Sie die oberen n-1-Platten vom Quellturm zum Hilfsturm 
  • Bewegen Sie die einzige verbleibende, n-te Festplatte (nach Schritt 1) ​​zum Ziel Tower
  • Bewegen Sie die n-1-Festplatten, die sich jetzt im Helmturm befinden, zum Ziel
    Turm, wobei der Quellturm als Helfer verwendet wird.

Quellcode in Java:  

private void towersOfHanoi(int n, char source, char destination, char helper) {
    //Base case, If there is only one disk move it direct from source to destination
    if(n==1){
        System.out.println("Move from "+source+" to "+destination);
    }
    else{
        //Step1: Move the top n-1 disks from source to helper
        towersOfHanoi(n-1, source, helper, destination);
        //Step2: Move the nth disk from source to destination
        System.out.println("Move from "+source+" to "+destination);
        /*Step3: Move the n-1 disks(those you moved from source to helper in step1) 
         * from helper to destination, using source(empty after step2) as helper
         */
        towersOfHanoi(n-1, helper, destination, source);
    }
}
1
bpjoshi

Hier geht die Erklärung. Schau dir das Bild an ->

 enter image description here

Durch den Aufruf von Movetower(3,a,b,c) möchten Sie alle 3 Scheiben von Turm A auf Turm B verschieben. Die sequentiellen Aufrufe sind also ->

1. Movetower(3,a,b,c)  // No Move needed
2. Movetower(2,a,c,b)  // No move needed
3. Movetower(1,a,b,c)  // Here is the time to move, move disc1 from a to b
4. Movetower(2,a,c,b)  // Returning to this call again, this is the time to move disc2 from a to c
5. Movetower(1,b,c,a)  // Again the time to move, this time disc1 from b to c
6. Movetower(3,a,b,c)  // Returning to this call again, this is the time to move disc3 from a to b
7. Movetower(2,c,b,a)  // Not the time to move
8. Movetower(1,c,a,b)  // Here is the time to move, move disc1 from c to a
9. Movetower(2,c,b,a)  // Returning to this call again, this is the time to move disc2 from c to b
10.Movetower(1,c,a,b)  // Here is the time to move, move disc1 from a to b

Ich hoffe es hilft :)

Für die Animation: https://www.cs.cmu.edu/~cburch/survey/recurse/hanoiex.html

0
jbsu32

Hier ist mein Lösungscode zu Towers of Hanoi Problem mit Rekursion mit Golang. `Paket Haupt

import "fmt"

func main() {
    toi(4, "src", "dest", "swap")
}

func toi(n int, from, to, swap string) {
    if n == 0 {
        return
    }
    if n == 1 {
        fmt.Printf("mov %v %v -> %v\n", n, from, to)
        return
    }
    toi(n-1, from, swap, to)
    fmt.Printf("mov %v %v -> %v\n", n, from, to)
    toi(n-1, swap, to, from)
}`
0
Gaurav Sinha

Dieses Python3-Beispiel verwendet eine rekursive Lösung:

# Hanoi towers puzzle
# for each n, you have to move n-1 disks off the n disk onto another peg
# then you move the n disk to a free peg
# then you move the n-1 disks on the other peg back onto the n disk

def hanoi(n):
    if n == 1:
        return 1
    else:
        return hanoi(n-1) + 1 + hanoi(n-1)


for i in range(1, 11):
    print(f"n={i}, moves={hanoi(i)}")

Ausgabe:

n=1, moves=1
n=2, moves=3
n=3, moves=7
n=4, moves=15
n=5, moves=31
n=6, moves=63
n=7, moves=127
n=8, moves=255
n=9, moves=511
n=10, moves=1023

Natürlich ist die effizienteste Methode, um herauszufinden, wie viele Schritte erforderlich sind, zu erkennen, dass die Antworten immer 1 weniger als 2 ^ n sind. Die mathematische Lösung lautet also 2 ^ n - 1

0
Angus Comber

Beim ersten rekursiven Aufruf werden alle Teile außer dem größten von der Quelle nach dest verschoben, wobei dest als Hilfsstapel verwendet wird. Wenn Sie fertig sind, werden alle Teile außer den größten liegen und der größte ist kostenlos. Jetzt können Sie den größten zu dest verschieben und einen weiteren rekursiven Aufruf verwenden, um alle Teile von by nach dest zu verschieben.

Die rekursiven Aufrufe wissen nichts über das größte Stück (d. H., Sie ignorieren es), aber das ist in Ordnung, da die rekursiven Aufrufe nur die Stücke behandeln, die kleiner sind, und somit auf das größte Stück frei verschoben werden können.

0
sepp2k

Als CS-Student haben Sie vielleicht schon von mathematischer Induktion gehört. Die rekursive Lösung von Tower of Hanoi funktioniert analog - es ist nur ein anderer Teil, mit B und C wirklich nicht verloren zu gehen, da der volle Turm endet.

0
weismat

Im einfachen Sinn besteht die Idee darin, einen anderen Turm unter den drei definierten Türmen in der gleichen Reihenfolge wie die vorhandenen Scheiben zu füllen, ohne dass eine größere Scheibe zu irgendeinem Zeitpunkt während des Verfahrens eine kleine Scheibe überlappt.

Seien 'A', 'B' und 'C' drei Türme. "A" ist der Turm, der anfangs "n" Scheiben enthält. 'B' kann als Zwischenturm verwendet werden und 'C' ist der Zielturm. 

Der Algo ist wie folgt:

  1. Bewegen Sie n-1 Scheiben mit 'C' vom Turm 'A' nach 'B'
  2. Verschieben Sie eine Disc von 'A' nach 'C'
  3. Bewegen Sie n-1 Scheiben mit 'A' vom Turm 'B' nach 'C'.

Der Code lautet in Java wie folgt:

öffentliche Klasse TowerOfHanoi {

public void TOH(int n, int A , int B , int C){
    if (n>0){
        TOH(n-1,A,C,B);
        System.out.println("Move a disk from tower "+A +" to tower " + C);
        TOH(n-1,B,A,C);
    }
}

public static void main(String[] args) {
    new TowerOfHanoi().TOH(3, 1, 2, 3);
}   

}

0
mohit verma