[PYTHON] Fordern Sie den Turm von Hanoi mit Wiederholungen + Stapel heraus
Guten Abend allerseits (* ^ - ^ *)
Neulich habe ich die Wiederholung in dem Artikel "Fordern Sie den Turm von Hanoi mit Wiederholung heraus" studiert. https://qiita.com/AKpirion/items/c0f7905c6227e086644e
- Ist es nicht möglich, Hyperlinks zu erstellen? ??
Also schrieb ich sofort die folgende Beschreibung, die mir @shiracamus sagte. Überlegen Sie, ob dies durch Hinzufügen eines Stapels erreicht werden kann.
hanoi_reference.py
def move(n, a, b, c):
"""Bewegen Sie n Festplatten von a nach b als temporären Unterschlupf nach c"""
if n > 1:
move(n - 1, a, c, b) #Speichern Sie bis b mit c als temporären Unterschlupf, mit Ausnahme des Bodens von a
print(f" {n}Nr. Disk{a}Von{c}Ziehen nach") #Bewegen Sie den Boden von a nach c
if n > 1:
move(n - 1, b, a, c) #Bewegen Sie sich mit a als vorübergehender Unterschlupf nach c, mit Ausnahme des Bodens, der in b gespeichert wurde
def hanoi(n):
print(f"{n}Schritte zum Verschieben einer Festplatte von A nach C.")
move(n, 'A', 'B', 'C')
if __name__ == '__main__':
hanoi(2)
hanoi(3)
Dieses Mal werden wir die beiden Festplatten wie im vorherigen Artikel verschieben.
Die rekursive Beschreibung kehrt immer zum Drucken zurück (f "Datenträger # {n} von {a} nach {c} verschieben").
In diesem Fall wird die if-Anweisung verwendet, um die Werte von {a} und {c} zu trennen.
Ich dachte, wenn Sie Push und Pop mischen, können Sie den Turm von Hanoi mit einem Stapel realisieren.
Zuerst habe ich dedizierte Stapel an den Positionen A, B und C vorbereitet.
hanoi_r1.py
class top:
def __init__(self,capacity:int = 2):
self.Astr = [2,1]
self.Bstr = [None] * capacity
self.Cstr = [None] * capacity
self.capa = capacity
self.Aptr = 0
self.Bptr = 0
self.Cptr = 0
Ich denke nicht, dass eine Ergänzung notwendig ist. Als nächstes kommt Push, aber im Grunde wird es nie voll, also Die Beschreibung kann einfach sein.
hanoi_r1.py
def Apush(self,value):
self.Astr[self.Aptr] = value
self.Aptr += 1
def Bpush(self,value):
self.Bstr[self.Bptr] = value
self.Bptr += 1
def Cpush(self,value):
self.Cstr[self.Cptr] = value
self.Cptr += 1
Da muss sich Pop keine Sorgen um Leer machen Die Beschreibung ist einfach.
hanoi_r1.py
def Apop(self):
self.Aptr -= 1
return self.Astr[self.Aptr]
def Bpop(self):
self.Bptr -= 1
return self.Bstr[self.Bptr]
def Cpop(self):
self.Cptr -= 1
return self.Cstr[self.Cptr]
Kein Problem, oder? Der Rest ist Bewegung.
hanoi_r1.py
def move(self,n,a,b,c):
if n>1:
top.move(self,n-1,a,c,b)
print(f"{n}Zu{a}Von{c}Was")
if a == "A" and c == "B":
top.Bpush(self,top.Apop(self))
top.Apush(self,None)
top.Apop(self)
top.view(self)
if a == "A" and c == "C":
top.Cpush(self,top.Apop(self))
top.Apush(self,None)
top.Apop(self)
top.view(self)
if a == "B" and c == "C":
top.Cpush(self,top.Bpop(self))
top.Bpush(self,None)
top.Bpop(self)
top.view(self)
if n>1:
top.move(self,n-1,b,a,c)
Wie ich am Anfang geschrieben habe, muss unbedingt gedruckt werden (f "Disk # {n} von {a} nach {c} verschieben") Da es herunterkommen wird, benutze ich if danach, um die Bedingungen zu klassifizieren. Mit drei Festplatten scheint es mehr Fälle zu geben (lacht) Ich frage mich, ob es einen guten Weg gibt. .. (´Д ｀) y━─┛ ~~
Um das Innere der if-Anweisung ein wenig mehr zu ergänzen, Da Push / Pop nur das Verhalten des Zeigers ptr verwaltet, Stellen Sie sicher, dass Sie den Wert des A / B / C-Stapelkörpers mit None überschreiben, da dies sonst nicht funktioniert. Also drücke ich Keine, Es erhöht ptr um 1 und verwendet dann pop, um es wiederherzustellen.
hanoi_r1.py
class top:
def __init__(self,capacity:int = 2):
self.Astr = [2,1]
self.Bstr = [None] * capacity
self.Cstr = [None] * capacity
self.capa = capacity
self.Aptr = 0
self.Bptr = 0
self.Cptr = 0
def Apush(self,value):
self.Astr[self.Aptr] = value
self.Aptr += 1
def Bpush(self,value):
self.Bstr[self.Bptr] = value
self.Bptr += 1
def Cpush(self,value):
self.Cstr[self.Cptr] = value
self.Cptr += 1
def Apop(self):
self.Aptr -= 1
return self.Astr[self.Aptr]
def Bpop(self):
self.Bptr -= 1
return self.Bstr[self.Bptr]
def Cpop(self):
self.Cptr -= 1
return self.Cstr[self.Cptr]
def view(self):
print(f"A = {self.Astr}")
print(f"B = {self.Bstr}")
print(f"C = {self.Cstr}")
def move(self,n,a,b,c):
if n>1:
top.move(self,n-1,a,c,b)
print(f"{n}Zu{a}Von{c}Was")
if a == "A" and c == "B":
top.Bpush(self,top.Apop(self))
top.Apush(self,None)
top.Apop(self)
top.view(self)
if a == "A" and c == "C":
top.Cpush(self,top.Apop(self))
top.Apush(self,None)
top.Apop(self)
top.view(self)
if a == "B" and c == "C":
top.Cpush(self,top.Bpop(self))
top.Bpush(self,None)
top.Bpop(self)
top.view(self)
if n>1:
top.move(self,n-1,b,a,c)
test = top()
if __name__ =="__main__":
print("default setting")
print("A = [2,1]")
print("B = [None,None]")
print("C = [None,None]")
test.move(2,"A","B","C")
Das Ausführungsergebnis ist hier.
default setting
A = [2,1]
B = [None,None]
C = [None,None]
1 von A nach B.
A = [2, None]
B = [1, None]
C = [None, None]
2 von A nach C.
A = [None, None]
B = [1, None]
C = [2, None]
1 von B nach C.
A = [None, None]
B = [None, None]
C = [2, 1]
N = 2 Nicht festgelegt, aber eine Konfiguration, die auch dann folgen kann, wenn sie frei geändert wird Ich werde es noch einmal betrachten. Selbst wenn die Anzahl der Blätter zunimmt, nimmt der Bewegungsort wahrscheinlich nicht zu Ich habe das Gefühl, dass ich etwas dagegen tun kann. Lass es uns eines Tages tun. .. (￣з￣)
--10/03 18:53
Das sportliche Treffen der Kinder war vorbei und er ging früh ins Bett. Ich habe Zeit. Ich werde es aktualisieren.
Der Inhalt des Updates besteht darin, eine Konfiguration zu berücksichtigen, mit der die Anzahl der Festplatten in N konvertiert werden kann. Wie ich beim letzten Mal angesprochen habe, nimmt die Anzahl der beweglichen Punkte nicht zu, selbst wenn die Anzahl der Festplatten zunimmt. Daher ist es in Ordnung, wenn alle Bewegungsmuster in der if-Anweisung aufgeführt sind.
A => B A => C B => C B => A C => A C => B
Wenn Sie den Fall teilen können, ist es nicht klug Das Problem kann behoben werden.
hanoi_stack_r1.py
if a == "A" and c == "B":
top.Bpush(self,top.Apop(self))
top.Apush(self,None)
top.Apop(self)
top.view(self)
if a == "A" and c == "C":
top.Cpush(self,top.Apop(self))
top.Apush(self,None)
top.Apop(self)
top.view(self)
if a == "B" and c == "C":
top.Cpush(self,top.Bpop(self))
top.Bpush(self,None)
top.Bpop(self)
top.view(self)
if a == "B" and c == "A":
top.Apush(self,top.Bpop(self))
top.Bpush(self,None)
top.Bpop(self)
top.view(self)
if a == "C" and c == "B":
top.Bpush(self,top.Cpop(self))
top.Cpush(self,None)
top.Cpop(self)
top.view(self)
if a == "C" and c == "A":
top.Apush(self,top.Cpop(self))
top.Cpush(self,None)
top.Cpop(self)
top.view(self)
Es ist in Ordnung. Als nächstes machen Sie die Anzahl der zu vorbereitenden Platten N variabel.
hanoi_stack_r1.py
class top:
def __init__(self,capacity):
self.Astr = [] * capacity #Keine ist auch Daten, also lassen Sie es hier leer
self.Bstr = [None] * capacity
self.Cstr = [None] * capacity
self.capa = capacity
self.Aptr = 0
self.Bptr = 0
self.Cptr = 0
for i in range(capacity): #Wenn Sie 4, 0 eingeben=> 1 => 2 =>3 und ändern
self.Astr.append(capacity-i) #Anzahl der Festplattenkapazität-Wenn ich, 4=> 3 => 2 =>1 kann Astr zugewiesen werden
top.view(self)
if __name__ =="__main__":
num = int(input("enter: ")) #Definieren Sie, wie viele Festplatten verwendet werden sollen
test = top(num) # def__init__Ersetzen Sie die Kapazität, den Anfangswert von, in num
test.move(num,"A","B","C") #num ist effektiv gleich der Tiefe des Stapels
Ist es nicht in Ordnung, überhaupt keine zu haben? !! (Lol) Ich habe es mit 5 Blättern versucht.
enter: 5
A = [5, 4, 3, 2, 1]
B = [None, None, None, None, None]
C = [None, None, None, None, None]
1 von A nach C.
A = [5, 4, 3, 2, None]
B = [None, None, None, None, None]
C = [1, None, None, None, None]
2 von A nach B.
A = [5, 4, 3, None, None]
B = [2, None, None, None, None]
C = [1, None, None, None, None]
1 von C nach B.
A = [5, 4, 3, None, None]
B = [2, 1, None, None, None]
C = [None, None, None, None, None]
3 von A nach C.
A = [5, 4, None, None, None]
B = [2, 1, None, None, None]
C = [3, None, None, None, None]
1 von B nach A.
A = [5, 4, 1, None, None]
B = [2, None, None, None, None]
C = [3, None, None, None, None]
2 von B nach C.
A = [5, 4, 1, None, None]
B = [None, None, None, None, None]
C = [3, 2, None, None, None]
1 von A nach C.
A = [5, 4, None, None, None]
B = [None, None, None, None, None]
C = [3, 2, 1, None, None]
4 von A nach B.
A = [5, None, None, None, None]
B = [4, None, None, None, None]
C = [3, 2, 1, None, None]
1 von C nach B.
A = [5, None, None, None, None]
B = [4, 1, None, None, None]
C = [3, 2, None, None, None]
2 von C nach A.
A = [5, 2, None, None, None]
B = [4, 1, None, None, None]
C = [3, None, None, None, None]
1 von B nach A.
A = [5, 2, 1, None, None]
B = [4, None, None, None, None]
C = [3, None, None, None, None]
3 von C nach B.
A = [5, 2, 1, None, None]
B = [4, 3, None, None, None]
C = [None, None, None, None, None]
1 von A nach C.
A = [5, 2, None, None, None]
B = [4, 3, None, None, None]
C = [1, None, None, None, None]
2 von A nach B.
A = [5, None, None, None, None]
B = [4, 3, 2, None, None]
C = [1, None, None, None, None]
1 von C nach B.
A = [5, None, None, None, None]
B = [4, 3, 2, 1, None]
C = [None, None, None, None, None]
5 von A nach C.
A = [None, None, None, None, None]
B = [4, 3, 2, 1, None]
C = [5, None, None, None, None]
1 von B nach A.
A = [1, None, None, None, None]
B = [4, 3, 2, None, None]
C = [5, None, None, None, None]
2 von B nach C.
A = [1, None, None, None, None]
B = [4, 3, None, None, None]
C = [5, 2, None, None, None]
1 von A nach C.
A = [None, None, None, None, None]
B = [4, 3, None, None, None]
C = [5, 2, 1, None, None]
3 von B nach A.
A = [3, None, None, None, None]
B = [4, None, None, None, None]
C = [5, 2, 1, None, None]
1 von C nach B.
A = [3, None, None, None, None]
B = [4, 1, None, None, None]
C = [5, 2, None, None, None]
2 von C nach A.
A = [3, 2, None, None, None]
B = [4, 1, None, None, None]
C = [5, None, None, None, None]
1 von B nach A.
A = [3, 2, 1, None, None]
B = [4, None, None, None, None]
C = [5, None, None, None, None]
4 von B nach C.
A = [3, 2, 1, None, None]
B = [None, None, None, None, None]
C = [5, 4, None, None, None]
1 von A nach C.
A = [3, 2, None, None, None]
B = [None, None, None, None, None]
C = [5, 4, 1, None, None]
2 von A nach B.
A = [3, None, None, None, None]
B = [2, None, None, None, None]
C = [5, 4, 1, None, None]
1 von C nach B.
A = [3, None, None, None, None]
B = [2, 1, None, None, None]
C = [5, 4, None, None, None]
3 von A nach C.
A = [None, None, None, None, None]
B = [2, 1, None, None, None]
C = [5, 4, 3, None, None]
1 von B nach A.
A = [1, None, None, None, None]
B = [2, None, None, None, None]
C = [5, 4, 3, None, None]
2 von B nach C.
A = [1, None, None, None, None]
B = [None, None, None, None, None]
C = [5, 4, 3, 2, None]
1 von A nach C.
A = [None, None, None, None, None]
B = [None, None, None, None, None]
C = [5, 4, 3, 2, 1]
Bitte überprüfen Sie, ob jemand ein Problem hat (lacht) Als nächstes folgt der Hinweis von @shiracamus Ich werde versuchen, eine pyhtonartige Beschreibung zu erstellen, die vereinfacht werden kann. Ich habe den Code von @ shiracamus gelesen. Nachdem ich es gelesen hatte, lachte ich. Python kann das (lacht). Ah ~ peinlich (* noωno) Ich schreibe einen Artikel zum Lernen Zu diesem Zeitpunkt ist es mir egal (lacht) Vorerst habe ich versucht, dies zuerst auszuführen.
test.py
tower = {"A": [*range(3, 0, -1)], "B": [], "C": []}
print(tower)
{'A': [3, 2, 1], 'B': [], 'C': []}
Was ist das ?! Magie ?? Übrigens, wenn Sie das * vor dem Bereich löschen. ..
{'A': [range(3, 0, -1)], 'B': [], 'C': []}
Ich war überrascht. Ich sehe, wenn Sie ein magisches "*" hinzufügen, Es wird zu einem Array (..) φ Memo Memo
Wie oben erwähnt, ist None auch eine Art von Daten Gehen Sie leer, ohne None zu verwenden. Es ist dasselbe.
Als nächstes folgt die Einführung von append () und pop (). append () verhält sich wie push. Darüber hinaus ist Pop genau wie die Idee von Pop. Darüber hinaus ist es bequem, die Daten für Pop abzurufen. Es ist im Begriff, die Daten zu löschen.
.. .. .. warte eine Minute. Bedeutet das, dass das vom Zeiger verwaltete Steuerelement nicht mehr benötigt wird ?! Lassen Sie es uns sofort optimieren, die Beschreibung von def __ init __.
test.py
def __init__(self,capacity):
###############################
self.Astr = [] * capacity #=> tower = {"A": [*range(n, 0, -1)], "B": [], "C": []}Ersetzen mit
self.Bstr = [None] * capacity
self.Cstr = [None] * capacity
self.capa = capacity
###############################
self.Aptr = 0 #=> append,Zeigerverwaltungsvariablen sind nicht erforderlich, da die Stapeloperation durch Pop realisiert wird.
self.Bptr = 0
self.Cptr = 0
##############################
for i in range(capacity): #=> "A": [*range(n, 0, -1)],Unnötig, weil es durch ersetzt wird
self.Astr.append(capacity-i)
top.view(self)
##############################
# || #
# \/ #
def __init__(self,n):
self.tower = {"A": [*range(n, 0, -1)], "B": [], "C": []}
Ich lachte w. Wenn Anhängen und Pop die Bewegungen des Stapels sind, Ist die folgende Beschreibung, die die Zeigeroperation zum Zeitpunkt von Push und Pop verwaltet, nicht unnötig?
test.py
#Alles unnötig!!!!#####################
def Apush(self,value):
self.Astr[self.Aptr] = value
self.Aptr += 1
def Bpush(self,value):
self.Bstr[self.Bptr] = value
self.Bptr += 1
def Cpush(self,value):
self.Cstr[self.Cptr] = value
self.Cptr += 1
def Apop(self):
self.Aptr -= 1
return self.Astr[self.Aptr]
def Bpop(self):
self.Bptr -= 1
return self.Bstr[self.Bptr]
def Cpop(self):
self.Cptr -= 1
return self.Cstr[self.Cptr]
################################
Der Turm ist definiert als der Anfangswert, Verschieben wir es sofort mit Append und Pop. Zusammenfassend ist dies geschehen.
test.py
class hanoi:
def __init__(self,n):
self.tower = {"A": [*range(n, 0, -1)], "B": [], "C": []}
def move(self,n,a,b,c):
if n>1:
hanoi.move(self,n-1,a,c,b)
print(f"{n}Zu{a}Von{c}Was")
self.tower[c].append(self.tower[a].pop())
if n>1:
hanoi.move(self,n-1,b,a,c)
Mein Verständnis ist, dass self verwendet wird, wenn Variablen zwischen defs in der Klasse übergeben werden. Wenn Sie also self.tower deklarieren, können Sie def move (self,) und self eingeben. Verstehen, dass Sie self.tower in die Def-Bewegung bringen können.
Was hanoi.move betrifft, ist es ein Bild, das def move in der Klasse hanoi aufruft. hanoi.move () Ich war überrascht. Möglicherweise müssen Sie etwas mehr Selbst lernen.
Ich werde als nächstes gehen. Die folgenden Funktionen werden definiert, um den Status jeder Box darzustellen.
test.py
def view(self):
print(f"A = {self.Astr}")
print(f"B = {self.Bstr}")
print(f"C = {self.Cstr}")
Jetzt, da Astr / Bstr / Cstr nicht mehr benötigt wird, Muss anders dargestellt werden. Ich bin nicht genial genug, um nur den Code zu verstehen, den ich erhalten habe Ich habe es nachgeschlagen. Es gab eine leicht verständliche Erklärung unten.
https://note.nkmk.me/python-dict-keys-values-items/
Demnach können der Name der Box und der Inhalt der Box durch Drehen der for-Anweisung ausgedrückt werden. Es war eine Sache.
test.py
def view(self):
for name,value in self.tower.items()
print(f"{name} = {value}")
Das war's. Lassen Sie es uns sofort einbauen.
test.py
class hanoi:
def __init__(self,n):
self.tower = {"A": [*range(n, 0, -1)], "B": [], "C": []}
def view(self):
for name,value in self.tower.items():
print(f"{name} = {value}")
def move(self,n,a,b,c):
if n>1:
hanoi.move(self,n-1,a,c,b)
print(f"{n}Zu{a}Von{c}Was")
self.tower[c].append(self.tower[a].pop())
hanoi.view(self)
if n>1:
hanoi.move(self,n-1,b,a,c)
Es ist einfach genug zu sterben. Das ganze Bild ist so.
hanoi_stack_r2.py
class hanoi:
def __init__(self,n):
self.tower = {"A": [*range(n, 0, -1)], "B": [], "C": []}
def view(self):
for name,value in self.tower.items():
print(f"{name} = {value}")
def move(self,n,a,b,c):
if n>1:
hanoi.move(self,n-1,a,c,b)
print(f"{n}Zu{a}Von{c}Was")
self.tower[c].append(self.tower[a].pop())
hanoi.view(self)
if n>1:
hanoi.move(self,n-1,b,a,c)
if __name__ =="__main__":
num = int(input("enter: "))
test = hanoi(num)
test.move(num,"A","B","C")
Vielen Dank an @shiracamus für die Gelegenheit, m (_ _) m zu studieren
Recommended Posts