Der Algorithmus, den wir gerade definiert haben, ist ein rekursiver Algorithmus um Türme mit n Scheiben zu verschieben. Wir werden diesen Algorithmus in Python als rekursive Funktion implementieren. Der zweite Schritt ist eine einfache Bewegung einer Scheibe, aber um die Schritte 1 und 3 zu verwirklichen, müssen wir den Algorithmus wieder auf sich selbst anwenden. Fortgeschrittene Themen: Die Türme von Hanoi. Die Berechnung endet in einer endlichen Anzahl von Schritten, da die Rekursion jedesmal mit einem um 1 verminderten Argument gegenüber der aufrufenden Funktion gestartet wird. Am Schluss ist noch eine einzelne zu bewegende Scheibe übrig. Rekursives Python-Programm
Das folgende in Python geschriebene Skript enthält eine rekursive Funktion namens "hanoi" zur Lösung des Spiels "Türme von Hanoi":
def hanoi(n, source, helper, target):
if n > 0:
# move tower of size n - 1 to helper:
hanoi(n - 1, source, target, helper)
# move disk from source peg to target peg
if source:
(())
# move tower of size n-1 from helper to target
hanoi(n - 1, helper, source, target)
source = [4, 3, 2, 1]
target = []
helper = []
hanoi(len(source), source, helper, target)
print source, helper, target
Anmerkung: AUX heißt in unserem Programm "helper".
- Türme von hanoi java pdf
Türme Von Hanoi Java Pdf
Das Spiel benutzt drei Stäbe und eine Anzahl von Scheiben z. B. 9, die auf die Stäbe gesteckt werden können. Anfänglich befinden sich alle Scheiben in absteigender Größe auf einem Stab angeordnet, d. die größte ist ganz unten und die kleinste ganz oben. Die Scheiben auf diesem Stab bilden einen konischen Turm. Die Aufgabe besteht darin, diesen Turm von einem Stab auf einen anderen zu bewegen unter Beachtung der folgenden Regeln:
In einem Zug darf immer nur eine Scheibe bewegt werden. Türme von hanoi java pdf. Es kann immer nur die oberste Scheibe eines Stapels bewegt werden. Eine Scheibe kann auf einem anderen Stab nur abgelegt werden, wenn der Stab leer ist, oder wenn die Scheibe kleiner als die oberste Scheibe des Zielstapels ist. Anzahl der Züge
Die minimal notwendige Anzahl von Zügen, die notwendig sind, um einen Turm der Größe n von einem Stab auf einen anderen unter Einhaltung der Regeln zu bewegen, lässt sich wie folgt berechnen:
2 n - 1
Lösungsfindung
Nach der obigen Formel wissen wir, dass wir 7 Züge benötigen, um einen Turm der Größe 3 von dem ganz linken Stab,
den wir im folgenden SOURCE nennen werden, auf den Stab ganz rechts, den wir TARGET nennen werden, zu bewegen.
Wir haben diese Funktion analog zum im vorigen Unterkapitel geschriebenen implementiert. Wir bewegen also zuerst einen Turm der Größe n-1 von "source" auf "helper". Dies geschieht durch den Aufruf
Danach bewegen wir die größte Scheibe von "source" auf "target mit der folgenden Anweisung:
Danach bewegen wir den Turm von "helper" nach "target", d. wir setzen ihn auf die größte Scheibe und sind dann fertig:
Wenn man nachvollziehen will, was während des Ablaufs passiert, so empfehlen wir die folgende geänderte Version unseres Python-Programmes zu verwenden. Bergervei/Java-Turm-von-Hanoi – ProgrammingWiki. Wir haben nicht nur ein paar prints eingebaut sondern auch die Datenstruktur geringfügig geändert. Wir übergeben jetzt nicht nur die Stäbe mit Scheiben sondern Tuple an die Funktion. Jedes Tuple enthält zum einen den Stab mit seinem Inhalt und als zweite Komponente, die Funktion des Stabes:
print "hanoi( ", n, source, helper, target, " called"
if source[0]:
disk = source[0]()
print "moving " + str(disk) + " from " + source[1] + " to " + target[1]
target[0](disk)
source = ([4, 3, 2, 1], "source")
target = ([], "target")
helper = ([], "helper")
hanoi(len(source[0]), source, helper, target)
Voriges Kapitel: Graphen in Python Nächstes Kapitel: Endlicher Automat