Gymnasium Löbau/Vertiefungsklasse 2010/Turtlegrafik (III)

Wiki-Quelltext dieser Seite.

<language>Java</language>
== 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:

<table>
<tr>
<td width="380" align="center" valign="top">[[Bild:Binärbaum1.gif]]</td>
<td width="920" align="left" valign="top">
<blockquote>
'''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.
</blockquote>
</td>
</tr>
</table>

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

<table>
<tr>
<td width="380" align="center" valign="top">
<canvas w="380" h="300"></canvas>
</td>
<td width="920" align="left" valign="top">

<code id="53762e8707c45">
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);
 }
}
</code>

<run id="53763a1548d3b">
canvas1.clear();
turtle1.move(190, 280);
baum(turtle1, 100, 6);
</run>
</td>
</tr>
</table>

Prozeduren, die mit sich selbst definiert werden, heißen ''rekursive''<sup>1)</sup> ''Prozeduren''.<br />
Rekursionen stellen ein ''leistungsstarkes und universelles Konzept'' zur Problemlösung dar.<br />

<sup>1)</sup> 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.

<table>
<tr>
<td width="380" align="center" valign="top">
<canvas w="380" h="300"></canvas>
</td>
<td width="920" align="left" valign="top">

<code id="537632102b602">
public void quadschnecke(Object turtle, double x) {
 if (x > 0) {
  turtle.forward(x);
  turtle.right(90);
  quadschnecke(turtle, x - 2);
 }
}
</code>

<run id="537632102b6a9">
canvas2.clear();
turtle2.move(100, 250);
quadschnecke(turtle2, 200);
</run>
</td>
</tr>
</table>

== Ein Ausflug in die Mathematik: Die rekursive Fakultätsfunktion ==

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

<blockquote>
<table>
<tr>
<td width="200" align="center">
<math>n!=1 \cdot 2 \cdot 3 \cdot ... \cdot n</math>
</td>
<td width="100" align="center">bzw. rekursiv:</td>
<td width="200" align="center">
<math>n!=\begin{cases}1,\mbox{wenn}\hspace{0.3em}n=0\\n \cdot (n-1)!\end{cases}</math>
</td>
</tr>
</table>
</blockquote>

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:'''

<code id="537682245c9f4">
public long fakultaet(int n) {
 if (n == 0)
  return 1;
 else
  return n * fakultaet(n - 1);
}
</code>

<run id="537682245ca97">
fakultaet(4);
</run>

'''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):

<blockquote>
[[Bild:Affenmodell1.gif]]
</blockquote>
''"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.<br /> 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. 

<ol>
<li>
=== Von rotierenden Quadraten zur Spiralarmgalaxie ===
...

</li>
<li>
=== Die Quadratpflanze ===

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

[[Bild: Quadratpflanze1.GIF]]

* Zeichne den nächsten (vierten) Schritt in der Entwicklung.
* Implementiere eine "Quadratpflanze" mit beliebiger Rekursionstiefe in der Turtlegrafik.
</li>
<li>
=== Die rekursive Summenfunktion ===
...

</li> 
</ol>

== 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''.<br />
Klassische selbstähnliche oder fraktale Figuren sind das Sierpinski-Dreieck und die Koch-Schneeflocke:

<blockquote>[[Bild:Sierpinski_Koch1.GIF]]</blockquote>

Beschreibe beide Fraktale verbal und implementiere diese mit der Turtlgrafik.<br />

Zur [[Gymnasium Löbau/Vertiefungsklasse 2010/Fraktale|Problemlösung]].