Exkurs - Implementierung in Python
Rekursion in Python
In Python können rekursive Algorithmen mit Funktionen, die sich selbst aufrufen, implementiert werden.
Damit können zum Beispiel die Zahlen 1, ..., n auch ohne Schleife ausgegeben werden.
Wenn mehr als eine Zahl ausgegeben werden soll, werden zuerst die Zahlen 1, ..., n-1 im rekursiven Aufruf ausgegeben.
Danach folgt die Ausgabe von n, die die Ausgabe komplettiert.
Im Basisfall n = 1 wird nur die Zahl 1 ausgegeben.
Man muss nur aufpassen, dass man auch einen Basisfall implementiert. Ansonsten versucht die Funktion immer weiter, sich selbst aufzurufen. Der Python-Interpreter bricht diese Versuche irgendwann ab und wirft einen Fehler.
Türme von Hanoi - Implementierung des rekursiven Algorithmus
Schon in Erkundung - Strategie für mehr als drei Scheiben haben wir uns gefragt:
bewegeMehrereScheiben(n, X, Z, Y) zu implementieren,
die eine passende Zugfolge für eine beliebige Scheibenanzahl n erzeugt?
Aufgabe 1
Aufgabe 2
- Teste die Ausgabe des Algorithmus für fünf oder mehr Scheiben mithilfe der Simulation.
- Zähle in der Ausgabe des Algorithmus für ein paar Eingaben die Anzahl der Züge. Schätze ab, wie lang die Mönche wohl brauchen, um einen 64-Scheiben-Turm umzustapeln. Wir gehen davon aus, dass sie zum Transport einer Scheibe mindestens 10 Sekunden benötigen.
