Exkurs - Implementierung in Python
Beispiel: Türme von Hanoi
Wir betrachten den rekursiven Algorithmus zum Problem Türme von Hanoi
:
ALGORTHMUS transportiere einen n-Scheiben-Turm von X über Y nach Z: wenn n > 1: transportiere einen (n-1)-Scheiben-Turm von X über Z nach Y transportiere eine Scheibe von X nach Z transportiere einen (n-1)-Scheiben-Turm von Y über X nach Z sonst: transportiere eine Scheibe von X nach Z
Diesen Algorithmus kann man wie folgt mit einer Funktion (Prozedur) in Python implementieren:
def transportiereTurm(n, x, y, z):
if n > 1:
transportiereTurm(n-1, x, z, y)
print("transportiere eine Scheibe von ", x, " nach ", z)
transportiereTurm(n-1, y, x, z)
else:
print("transportiere eine Scheibe von ", x, " nach ", z)
Wenn man diese Prozedur ausführt, dann erhält man z. B. folgende Ausgaben.
>>> transportiereTurm(3, 'A', 'B', 'C')
transportiere eine Scheibe von A nach C
transportiere eine Scheibe von A nach B
transportiere eine Scheibe von C nach B
transportiere eine Scheibe von A nach C
transportiere eine Scheibe von B nach A
transportiere eine Scheibe von B nach C
transportiere eine Scheibe von A nach C
Aufgabe 1
(a) Teste selbst die oben gezeigte Funktion. Teste sie zunächst mit einem 3-Scheiben-Turm. Vergleiche die Ausgaben der Funktion mit dem im letzten Abschnitt selbst schrittweise ausgeführten Algorithmus.
Ausführungstiefe 3:
transportiere einen 3-Scheiben-Turm von A über B nach C: transportiere einen 2-Scheiben-Turm von A über C nach B: transportiere einen 1-Scheiben-Turm von A über B nach C: transportiere eine Scheibe von A nach C transportiere eine Scheibe von A nach B transportiere einen 1-Scheiben-Turm von C über A nach B: transportiere eine Scheibe von C nach B transportiere eine Scheibe von A nach C transportiere einen 2-Scheiben-Turm von B über A nach C: transportiere einen 1-Scheiben-Turm von B über C nach A: transportiere eine Scheibe von B nach A transportiere eine Scheibe von B nach C transportiere einen 1-Scheiben-Turm von A über B nach C: transportiere eine Scheibe von A nach C
(b) Teste die oben gezeigte Funktion auch mit einem 4-Scheiben-Turm oder einem 5-Scheiben-Turm. Überprüfe, ob die Ausgaben tatsächlich eine korrekte Lösung beschreiben.