Turtlegrafik (III)

Aus ProgrammingWiki

Inhaltsverzeichnis 1 Selbstähnlichkeiten 1.1 Der Binärbaum 1.2 Die "Quadratschnecke" 2 Ein Ausflug in die Mathematik: Die rekursive Fakultätsfunktion 3 Das Affenmodell 4 Aufgaben 4.1 Von rotierenden Quadraten zur Spiralarmgalaxie 4.2 Die "Quadratpflanze" 4.3 Die rekursive Summenfunktion 4.4 Der Turm von Hanoi 5 Zum Weiterarbeiten 5.1 Fraktale

Selbstähnlichkeiten

Der Binärbaum

Zunächst betrachten wir das nachfolgende Grafikobjekt, das wir als Binärbaum bezeichnen wollen. Dabei fällt auf, dass jeder Ast wieder ein kleiner Binärbaum ist. Wir wollen diese Selbstähnlichkeit zu seiner Beschreibung ausnutzen:

Beschreibung: Der einfachste Binärbaum besteht aus einem Stamm. Jeder andere Binärbaum besteht aus einem Stamm sowie einem vereinfachten linken und einem vereinfachten rechten Binärbaum.

Wir stellen fest, dass es durchaus sinnvoll sein kann, Objekte mit sich selbst zu beschreiben.
Mit der Turtlegrafik wollen wir eine gleichwertige Implementation vornehmen. Dazu definieren wir den Baum mit sich selbst.

public void baum(Object turtle, double x, int n) { if (n > 0) { turtle.forward(x); turtle.left(45); baum(turtle, 2 * x / 3, n - 1); turtle.right(90); baum(turtle, 2 * x / 3, n - 1); turtle.left(45); turtle.backward(x); } } canvas1.clear(); turtle1.move(190, 280); baum(turtle1, 100, 6); ausführen

Prozeduren, die mit sich selbst definiert werden, heißen rekursive¹⁾ Prozeduren.
Rekursionen stellen ein leistungsstarkes und universelles Konzept zur Problemlösung dar.

¹⁾ recurrere (lat.): "zurücklaufen"

Die "Quadratschnecke"

Beschreibung:

• Die einfachste Quadratschnecke besteht aus einer Strecke.
• Jede andere Quadratschnecke besteht aus einer Strecke, einer Drehung um 90° sowie einer etwas verkürzten Quadratschnecke.

public void quadschnecke(Object turtle, double x) { if (x > 0) { turtle.forward(x); turtle.right(90); quadschnecke(turtle, x - 2); } } canvas2.clear(); turtle2.move(100, 250); quadschnecke(turtle2, 200); ausführen

Ein Ausflug in die Mathematik: Die rekursive Fakultätsfunktion

Zum besseren Verständnis analysieren wir die mathematische Definition der Fakultätsfunktion:

bzw. rekursiv:

In der zweiten Beschreibung ist die Definition mit sich selbst offensichtlich.

Beschreibung:

• Die Fakultät einer Zahl ist 1, wenn die Zahl 0 ist,
• anderenfalls berechnet sie sich aus dem Produkt dieser Zahl mit der Fakultät ihres Vorgängers.

Implementation:

public long fakultaet(int n) { if (n == 0) return 1; else return n * fakultaet(n - 1); }

fakultaet(4);

ausführen

Beachte: Rekursive Prozeduren enthalten neben dem rekursiven Prozeduraufruf immer eine Elementarbedingung!

Das Affenmodell

Eine schöne Interpretation des rekursiven Prozeduraufrufes finden wir in dem Buch "Rekursionen - Ein didaktischer Zugang mit Funktionen" von Chr. Wagenknecht (Dümmler Verlag, Bonn 1994, S. 42):

"Der Auftrag, der von außen dem höchsten Oberaffen übergeben wurde, wird von diesem nicht vollständig bearbeitet, sondern in etwas abgeschwächter Form dem untergebenen Affen übergeben. Dieser verhält sich ebenso zu seinem Untergebenen. Der letzte Affe in dieser Hierarchie kann den ihm übergebenen Auftrag erfüllen und dem übergeordneten Affen übergeben. Jeder weitere Affe hat die Pflicht, das Resultat der Erledigung seines Auftrages seinem Auftraggeber zu übergeben. Schließlich kann der Ranghöchste sein Ergebnis abliefern.
Parallelen zu Einrichtungen, Ämtern und Institutionen unserer Gesellschaft sind unbeabsichtigt oder rein zufällig."

Aufgaben

Die Prozeduren zu den nachfolgenden Aufgaben können entweder unter dem eigenen Benutzernamen oder auf der unten verlinkten Lösungsseite implementiert werden.

1. Von rotierenden Quadraten zur Spiralarmgalaxie

   Zunächst soll ein Quadrat um seinen Eckpunkt gedreht und dabei seine Größe verkleinert werden.
   Wenn man mehrere dieser Drehungen zusammensetzt, erinnert das Gesamtbild an eine Spiralarmgalaxie (vgl. Abbildungen).

   

   Entwickle eine rekursive Prozedur zur Darstellung eines "Spiralarms".
   Zur Darstellung der "Spiralarmgalaxie" kannst Du diese Prozedur dann in einer Zählschleife aufrufen.

2. Die "Quadratpflanze"

   Die Bilder zeigen die Entstehung einer Quadratpflanze.
   Bei jedem neuen Aufruf beträgt die Seitenlänge jeweils nur noch ein Drittel der vorherigen.
   

   

   • Zeichne den nächsten (vierten) Schritt in der Entwicklung.
   • Implementiere eine Quadratpflanze mit beliebiger Rekursionstiefe in der Turtlegrafik.

3. Die rekursive Summenfunktion

   Auf unserer Startseite wird die Summe von natürlichen Zahlen iterativ bestimmt, d.h. schrittweise wird das Ergebnis in einer Zählschleife ermittelt.
   Berechne nun diese Summe nach dem Vorbild der Fakultätsfunktion rekursiv.

4. Der Turm von Hanoi

   Vermutlich stammt dieses Spiel von dem französischen Mathematiker Édouard Lucas (* 4. April 1842; † 3. Oktober 1891), bei dem ein Turm aus einzelnen Scheiben von nach unter Nutzung des Hilfsplatzes umgesetzt werden soll. Dabei darf immer nur eine Scheibe bewegt werden. Außerdem darf nie eine größere Scheibe auf einer kleineren liegen. Lucas dachte sich dazu die Geschichte aus, dass indische Mönche im großen Tempel zu Benares, im Mittelpunkt der Welt, einen Turm aus 64 goldenen Scheiben versetzen müssten. Wenn ihnen das gelungen sei, wäre das Ende der Welt gekommen.

   Turm von Hanoi

   Gegeben ist nun die folgende Implementation:

   int count = 0; public void verschiebe(int n, String start, String h, String ziel) { if (n > 0) { verschiebe(n - 1, start, ziel, h); count++; System.out.println("Scheibe " + n + ": " + start + " --> " + ziel); verschiebe(n - 1, h, start, ziel); } } public void hanoi(int n) { verschiebe(n, "A", "H", "B"); System.out.println("--> " + count + " Bewegung(en)"); }

   • Teste zunächst die Prozedur hanoi mit kleinen Argumenten.

   hanoi(3);

   ausführen

   Beschreibe die Spielstrategie (d.h. den Lösungsalgorithmus) verbal. Ermittle den Zusammenhang, der zwischen der Anzahl der Scheiben und der Anzahl der erforderlichen Bewegungen besteht. In wie vielen Jahren "droht" das Ende der Welt, wenn die indischen Mönche im Tempel zu Benares für die Bewegung jeder einzelnen Scheibe eine Sekunde benötigen würden?

   Turm von Hanoi mit 3 Scheiben

Zu den Lösungen der Aufgaben.

Zum Weiterarbeiten

Fraktale

Mit selbstähnlichen Figuren bzw. Objekten beschäftigt sich heute ein ganzes Teilgebiet der Mathematik, die fraktale Geometrie. Ihre Untersuchungsergebnisse haben z.B. einen wesentlichen Einfluss auf die Chaosforschung.
Klassische selbstähnliche oder fraktale Figuren sind das Sierpinski-Dreieck und die Koch-Schneeflocke:

Beschreibe beide Fraktale verbal und implementiere diese mit der Turtlegrafik.

Zur Problemlösung.