1. 1. Einführung

Rekursive Funktionen können das erste Hindernis für die Programmierung sein. Lassen Sie uns die rekursive Funktion beherrschen, während wir den Turm von Hanoi mit Python lösen.

Rekursive Funktionen wie Matroschka haben eine verschachtelte Programmstruktur. Bitte lesen Sie auf jeden Fall die folgende Erklärung, während Sie sich Matroschka vorstellen. マトリョーシカ.jpg

2. Hanoi Tower

Siehe unten für den Turm von Hanoi. Turm von Hanoi ハノイの塔.jpg

Kurz gesagt, es gibt drei Stöcke, die von einem Brett durchbohrt werden können. Auf der linken Seite befinden sich mehrere Tafeln. Die Größe der Platte ist unten am größten und wird oben kleiner. Ich möchte die Bretter einzeln verschieben und schließlich alle Bretter von links in die mittlere Leiste verschieben. Eine große Platte kann jedoch nicht auf eine kleine Platte gelegt werden.

Beim Erlernen der Programmierung ist es ein Problem, das mit einer rekursiven Funktion gelöst werden muss.

3. 3. Denkweise

Einer ist super einfach. Bewegen Sie sich von links in die Mitte und Sie sind fertig. Der Punkt ist der Fall von zwei Blättern. Bewegen Sie das kleine Brett in der linken Leiste plötzlich nicht mehr in die Mitte. (1) Zunächst wird die kleine Platte einmal auf die Arbeitsstange auf der rechten Seite übertragen. (2) Bewegen Sie dann das große Brett links links in die Mitte. (3) Bewegen Sie danach das kleine Brett von rechts in die Mitte, und es ist in Ordnung.

Mit anderen Worten, n Bretter (in diesem Fall 2 Bretter), um alles von links nach Mitte zu bewegen, (1) n-1 Bretter (in diesem Fall 1 Brett) mit Ausnahme des größten Brettes unten Es ist notwendig, einmal von links nach rechts zur Arbeitsstange zu gehen. (2) Nachdem Sie die größte Platte unten von links nach Mitte bewegt haben, (3) alle n-1-Platten (in diesem Fall eine) auf der rechten Arbeitsstange. Wenn Sie es in die Mitte verschieben, ist es in Ordnung.

In der folgenden Beschreibung werden die obigen (1) bis (3) wiederholt beschrieben. (1) bis (3), die in der folgenden Erklärung erscheinen, haben grundsätzlich die gleiche Bedeutung wie (1) bis (3) oben. "Wohin wohin" ändert sich jedoch je nach Fall in "links, Mitte, rechts".

4. Rekursive Lösung

Das folgende ist das Lösungsprogramm für den Turm in Hanoi. Ich werde es später ausführen, aber wenn Sie es verwenden, ersetzen Sie N durch die Anzahl der Karten.

start=list(range(N,0,-1));end=[];tmp=[];i=0  #1
def print_hanoi(): #2
    print(start,end,tmp)
def hanoi(n,start,end,tmp): #3
    if n<=0:        return  #4
    hanoi(n-1,start,tmp,end)  #5
    end.append(start.pop())   #6
    print_hanoi()              #7
    global i; i+=1             #8
    print('Das obige ist',i,'Zustand nach der zweiten Operation')   #9
    hanoi(n-1,tmp,end,start)   #10
print_hanoi()                  #11
print('Das Obige ist der Ausgangszustand')       #12
hanoi(N,start,end,tmp)         #13

Ich werde es kurz erklären. Die Nummern entsprechen den im Programm mit # gekennzeichneten Teilen.

1. start ist eine Liste, die das Board darstellt, das zuerst in der linken Leiste steckt. Im Ausgangszustand ist der Boden der größte, die Liste ist um 1 kleiner und der letzte ist 1.

Ende ist eine Liste, die das Board zeigt, das im mittleren Stick steckt und das Sie endgültig übertragen möchten. Zunächst steckt nichts fest, also eine leere Liste.

tmp ist eine Liste, die das Board zeigt, das für die Arbeit auf der rechten Seite im Stick steckt. Dies ist auch eine leere Liste, da zunächst nichts feststeckt.

i wird eingestellt, um die Anzahl der Operationen anzuzeigen.

Repräsentiert einen Zustand. Die Bretter, die nacheinander in den Sticks "links, mittel, rechts" stecken, werden in einer Liste angezeigt.
1. Dies ist die Funktion, die den Turm in Hanoi löst. Da es jedoch eine rekursive Funktion verwendet, ist es wie Matroschka verschachtelt. Bitte achten Sie auf das Argument. Das erste n ist die Anzahl der Bretter. Als nächstes ist Start und ich möchte es zum nächsten Ende verschieben. Der letzte ist tmp.
Dies ist die Basisbeendigungsbedingung. Wenn die Anzahl der zu bewegenden Bretter 0 wird, endet der Vorgang. Wenn Sie die Basisbeendigungsbedingung vergessen, geraten Sie in eine Endlosschleife. Seien Sie also vorsichtig.

Die Funktion von 5.3 wird rekursiv verwendet. Die Funktion von 3 ist jedoch so definiert, dass alle n Blätter des ersten Arguments vom Anfang des zweiten Arguments bis zum Ende des dritten Arguments verschoben werden. (Das vierte Argument ist tmp für die Arbeit.)

Hier ** (1) Alle verbleibenden n-1 Blätter (erstes Argument) mit Ausnahme des unteren n werden vorübergehend vom Start (zweites Argument) nach tmp (drittes Argument) verschoben. ** (Das vierte Argument ist das verbleibende Argumentende.)

** Auf diese Weise werden n-1 Blätter von oben nach tmp verschoben, sodass Sie n nach unten verschieben können. ** ** **

Da ich in 6.5 n-1 Blätter von oben nach tmp verschoben habe, verbleibt nur das untere n in der linken Startleiste. (2) Nehmen Sie das untere Brett heraus und verschieben Sie es in "start.pop ()" und in die mittlere Endleiste "end.append ()" (zur Liste hinzufügen).

Drucken Sie den Status hier aus.
Zählen Sie die Anzahl der Male hoch.
Drucken Sie die Anzahl der Vorgänge nach dem Vorgang aus, um das Verständnis zu erleichtern.
** Das größte Brett von 6 ist in die Mitte gerückt. (3) Übertragen Sie alle n-1-Platten auf der rechten Arbeitsstange auf die größte Platte. Wenn Sie sich die Argumente ansehen, können Sie sehen, was Sie tun. ** ** **
Drucken Sie hier den Ausgangszustand aus.
Drucken Sie Kommentare zum leichteren Verständnis.
Tatsächliche Ausführung. N wird angegeben, wenn es tatsächlich verwendet wird.

5. Lass es uns tatsächlich versuchen

1. Zuallererst, wenn es ein Board gibt. Ich denke nicht, dass es notwendig ist, aber sei vorsichtig mit allem. N wird zu Beginn des Programms angegeben.

N=1;start=list(range(N,0,-1));end=[];tmp=[];i=0  #1
def print_hanoi(): #2
    print(start,end,tmp)
def hanoi(n,start,end,tmp): #3
    if n<=0:        return  #4
    hanoi(n-1,start,tmp,end)  #5
    end.append(start.pop())   #6
    print_hanoi()              #7
    global i; i+=1             #8
    print('Das obige ist',i,'Zustand nach der zweiten Operation')   #9
    hanoi(n-1,tmp,end,start)   #10
print_hanoi()                  #11
print('Das Obige ist der Ausgangszustand')       #12
hanoi(N,start,end,tmp)         #13

Das Ergebnis ist wie folgt. Bewegen Sie sich von links in die Mitte und Sie sind fertig.

Hier wird nur der in der "Idee" von 3 beschriebene Teil (2) ausgeführt. Wie Sie sehen können, wenn Sie sich # 5 (1) und # 10 (2) ansehen, wird n-1 zu 0 und in # 4 wird nichts ausgeführt.

[1] [] []
Das Obige ist der Ausgangszustand
[] [1] []
Das Obige ist der Zustand nach der ersten Operation

Als nächstes folgen zwei Fälle. Im Gegensatz zu einem Fall wird für den zweiten und die folgenden Fälle der richtige Arbeitsstab verwendet.

N=2;start=list(range(N,0,-1));end=[];tmp=[];i=0  #1
def print_hanoi(): #2
    print(start,end,tmp)
def hanoi(n,start,end,tmp): #3
    if n<=0:        return  #4
    hanoi(n-1,start,tmp,end)  #5
    end.append(start.pop())   #6
    print_hanoi()              #7
    global i; i+=1             #8
    print('Das obige ist',i,'Zustand nach der zweiten Operation')   #9
    hanoi(n-1,tmp,end,start)   #10
print_hanoi()                  #11
print('Das Obige ist der Ausgangszustand')       #12
hanoi(N,start,end,tmp)         #13

Das Ergebnis ist wie folgt. Die Zahlen geben die Größe der Tafel an. Die Zahlen in der Liste werden in der angegebenen Reihenfolge ausgegeben. Mit anderen Worten, für die Regeln des Turms in Hanoi ist es erforderlich, dass die Nummern in der Liste in absteigender Reihenfolge angeordnet sind. In zwei Fällen (1) ** Bewegen Sie zuerst die kleine Platte von links nach rechts zur Arbeitsstange. ** (Erste Operation) (2) Und ** Auf diese Weise kann das große Brett links in die Mitte verschoben werden. ** (Zweite Operation) (3) ** Bewegen Sie zum Schluss die kleine Platte rechts auf die große Platte in der Mitte, und es ist in Ordnung. ** (3. Operation)

[2, 1] [] []
Das Obige ist der Ausgangszustand
[2] [] [1]
Das Obige ist der Zustand nach der ersten Operation
[] [2] [1]
Das Obige ist der Zustand nach der zweiten Operation
[] [2, 1] []
Das Obige ist der Zustand nach der dritten Operation

Das Programm entfällt nach 3,3 Blatt. Es ist in Ordnung, wenn Sie die Anzahl der Blätter ändern, die N zugewiesen werden sollen. Das Ergebnis ist wie folgt.

[3, 2, 1] [] []
Das Obige ist der Ausgangszustand
[3, 2] [1] []
Das Obige ist der Zustand nach der ersten Operation
[3] [1] [2]
Das Obige ist der Zustand nach der zweiten Operation
[3] [] [2, 1]
Das Obige ist der Zustand nach der dritten Operation
[] [3] [2, 1]
Das Obige ist der Zustand nach der 4. Operation
[1] [3] [2]
Das Obige ist der Zustand nach der 5. Operation
[1] [3, 2] []
Das Obige ist der Zustand nach der 6. Operation
[] [3, 2, 1] []
Das Obige ist der Zustand nach der 7. Operation

(1) ** Bei der ersten bis dritten Operation werden zwei Blätter (dh n-1 Blätter) auf die richtige Arbeitsstange übertragen. Das erste bis dritte Mal umfasst (1) bis (3) bei zwei Blättern. ** Natürlich sind die Details von "wohin wohin" von Fall zu Fall.

(2) Dann wird in der ** 4. Operation das größte 3. Blatt (dh das n-te Blatt) von links in die Mitte verschoben. ** ** **

(3) Danach bewegen Sie in den Operationen vom ** 5. bis 7. die 2 Blätter (dh n-1 Blätter) auf der rechten Seite auf die größte Platte in der Mitte, und Sie sind fertig. Das 5. bis 7. Mal enthält auch (1) bis (3) bei zwei Blättern. ** Natürlich sind die Details von "wohin wohin" von Fall zu Fall.

Ich möchte, dass Sie hier vorsichtig sind, wenn Sie die beiden Teile auf den richtigen Arbeitsstab in (1) übertragen. ** Im Falle des Verschiebens der beiden in 2 fertiggestellten Teile von links nach Mitte wurde die rechte Seite zur Arbeit. Wenn Sie jedoch zwei Blätter mit drei Blättern (1) von links nach rechts bewegen, ist das Zentrum natürlich für die Arbeit vorgesehen. Daher wird die kleinste Platine in der ersten Operation in die Mitte verschoben. ** ** **

** Gleiches gilt, wenn in (3) zwei Blätter von rechts in die Mitte verschoben werden. Hier ist links die Arbeit, so dass in der fünften Operation die kleinste Platte von rechts nach links bewegt wird. ** ** **

Lassen Sie uns mit 4 Fällen am Ende beenden.

[4, 3, 2, 1] [] []
Das Obige ist der Ausgangszustand
[4, 3, 2] [] [1]
Das Obige ist der Zustand nach der ersten Operation
[4, 3] [2] [1]
Das Obige ist der Zustand nach der zweiten Operation
[4, 3] [2, 1] []
Das Obige ist der Zustand nach der dritten Operation
[4] [2, 1] [3]
Das Obige ist der Zustand nach der 4. Operation
[4, 1] [2] [3]
Das Obige ist der Zustand nach der 5. Operation
[4, 1] [] [3, 2]
Das Obige ist der Zustand nach der 6. Operation
[4] [] [3, 2, 1]
Das Obige ist der Zustand nach der 7. Operation
[] [4] [3, 2, 1]
Das Obige ist der Zustand nach der 8. Operation
[] [4, 1] [3, 2]
Das Obige ist der Zustand nach der 9. Operation
[2] [4, 1] [3]
Das Obige ist der Zustand nach der 10. Operation
[2, 1] [4] [3]
Das Obige ist der Zustand nach der 11. Operation
[2, 1] [4, 3] []
Das Obige ist der Zustand nach der 12. Operation
[2] [4, 3] [1]
Das Obige ist der Zustand nach der 13. Operation
[] [4, 3, 2] [1]
Das Obige ist der Zustand nach der 14. Operation
[] [4, 3, 2, 1] []
Das Obige ist der Zustand nach der 15. Operation

(1) ** Bei den Operationen vom 1. bis zum 7. werden 3 Blätter (dh n-1 Blätter) auf die rechte Arbeitsstange übertragen. Das erste bis siebte Mal umfasst (1) bis (3) bei drei Blättern. Dann umfasst (1) im Fall von 3 Blättern (1) bis (3) im Fall von 2 Blättern, und (1) im Fall von 2 Blättern ist auch in (3) im Fall von 3 Blättern enthalten. ) Bis (3) sind enthalten. ** ** **

(2) Dann wird in der ** 8. Operation das größte 4. Blatt (dh das n-te Blatt) von links nach Mitte verschoben. ** ** **

(3) ** Danach bewegen Sie im 9. bis 15. Arbeitsgang die 3 Blätter (dh n-1 Blätter) auf der rechten Seite auf die größte Platte in der Mitte, und Sie sind fertig. Das 9. bis 15. Mal enthält (1) bis (3) bei drei Blättern. Dann umfasst (1) im Fall von 3 Blättern (1) bis (3) im Fall von 2 Blättern, und (1) im Fall von 2 Blättern ist auch in (3) im Fall von 3 Blättern enthalten. ) Bis (3) sind enthalten. ** ** **

Diesmal sowie bei 3 Blättern ändert sich die Arbeitsnutzung.

6. Zusammenfassung

Die Rolle der Arbeit im Turm in Hanoi ändert sich je nach Anzahl der Bretter. Ich möchte jedoch, dass Sie auf die Teile (1), (2) und (3) achten, die im 2., 3. und 4. Blatt von 5 beschrieben sind. (1) ** Übertragen Sie zuerst n-1 Blätter von oben für die Arbeit von links nach rechts. ** (2) ** Auf diese Weise kann das große Brett unten von links in die Mitte verschoben werden. ** (3) ** Wenn Sie schließlich n-1 Blätter von oben nach rechts von der Arbeit rechts verschieben, ist dies in Ordnung. ** ** **

Apropos Programm von 4, (1) entspricht 5, (2) entspricht 6 und (3) entspricht 10. Es ist die rekursive Funktion, die verwendet wird, um den Turm in Hanoi zu lösen, die diese Operation wiederholt, wie Matroschka. (Um genau zu sein, sind die reinen rekursiven Teile (1) und (3).)

7. Referenzseite

Die folgenden Sites sind in C ++ geschrieben, aber sie sind sehr hilfreiche Sites. Der Autor ist derjenige, den ich persönlich respektiere.

Welche Art von Welt wird sich erweitern, wenn Sie rekursive Funktionen lernen

[PYTHON] [Für Anfänger] Rekursive Funktion (Der Turm in Hanoi ist leicht zu verstehen!)