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.