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 Quersumme einer Zahl auch ganz ohne Schleife berechnen. Eine Möglichkeit
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:
Ist es möglich, eine verallgemeinerte Funktion
bewegeMehrereScheiben(n, X, Z, Y) zu implementieren,
die eine passende Zugfolge für eine beliebige Scheibenanzahl n erzeugt?
Aufgabe 1
Implementiere den rekursiven Algorithmus als Python-Programm.
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.