Informatik
Startseite > Unterricht > Algorithmen und Datenstrukturen > Rekursion
Beispiel 3: Sierpinski-Dreieck
Das Sierpinski-Dreieck (engl.: Sierpinski gasket) ist nach dem polnischen Mathematiker Waclaw Sierpinski (1882-1969) benannt. Es ist ein sogenanntes Fraktal.
Die Konstruktion verläuft wie folgt: Ein gleichseitiges Dreieck wird in vier gleiche Teile geteilt, von denen man das mittlere einfärbt. Dieser Vorgang wird nun immer wieder mit allen nicht eingefärbten Dreiecken wiederholt. Damit wird, was für Fraktale typisch ist, die Struktur unendlich tief, d. h. auch bei beliebig tiefen Hereinzoomen verliert das Fraktal nicht seine komplizierte Form.
Die rekursive Vorschrift lautet: Um ein Dreieck der Tiefe n zu zeichnen, zeichne man drei Dreiecke der Tiefe n - 1 mit halber Seitenlänge, die in den Ecken des ursprünglichen Dreiecks sitzen.
Auf der französischen Seite http://www.enseignement.polytechnique.fr haben wir ein Java-Programm gefunden, das obige rekursive Vorschrift realisiert. Wir mussten es jedoch umschreiben. Unser Programm lautet:
import java.io.*;
import java.awt.*;
import java.awt.event.*;class Spinne {
// definiert "Spinnengrafik" (entspricht Turtlegrafik)
Container c;
Graphics g;double x, y, richtung;
boolean stiftunten;
Color farbe;Spinne (Container c0, double x0, double y0, double r0) {
c = c0; g = c0.getGraphics();
x = x0; y = y0;
richtung = r0;
stiftunten = true;
farbe = Color.black;
} // Ende Konstruktor Spinnevoid hebeStift()
{stiftunten = false;}void senkeStift()
{stiftunten = true;}void links (double winkel)
{richtung = Math.IEEEremainder(richtung + winkel, 360.0);}void rechts (double winkel)
{links(-winkel);}void vor (double länge) {
double x1, y1;
x1 = x + länge * Math.cos(richtung * Math.PI/180.0);
y1 = y - länge * Math.sin(richtung * Math.PI/180.0);
if (stiftunten)
g.drawLine((int) Math.round(x), (int) Math.round(y),
(int) Math.round(x1), (int) Math.round(y1));
x = x1; y = y1;
} // Ende vorvoid zurück (double länge)
{vor(-länge);}} // Ende Spinne
class Sierpinski extends Frame {
Spinne silke;
static int tiefe;
Sierpinski() {
setTitle("Sierpinski-Dreieck");
setBackground(new Color(250, 235, 200));
setSize(500, 500);
setLocation(20, 20);
setVisible(true);
addWindowListener(new WindowAdapter() {
public void windowClosing(WindowEvent e)
{System.exit(0);}});
} // Ende Konstruktor Sierpinskipublic void paint (Graphics g) {
silke = new Spinne(this, 200, 300, -30);
zeichneDreieck(tiefe, 90);
} // Ende paintvoid zeichneDreieck (int stufe, double länge) {
if (stufe > 0)
for (int i = 0; i < 3; i = i + 1) {
silke.vor(länge);
zeichneDreieck(stufe - 1, länge * 0.5);
silke.zurück(länge);
silke.links(120);
} // Ende for
} // Ende zeichne Dreieckstatic void main (String[] xy) throws IOException {
InputStreamReader lies = new InputStreamReader(System.in);
BufferedReader eing = new BufferedReader(lies);System.out.println("\nZeichnung eines Sierpinski-Dreiecks\n");
System.out.print("Tiefe (z. B. 6): ");
tiefe = Integer.parseInt(eing.readLine());new Sierpinski();
} // Ende main} // Ende Sierpinski
Der Aufruf java Sierpinski liefert folgende Grafik:
Erläuterungen zum Programm:
(...)
Obiges Bild erinnert uns an das sogenannte Pascal-Dreieck, das wir im Mathematikunterricht kennengelernt haben. In der Tat fanden wir auf einigen Internet-Seiten Hinweise auf eine interessante "Dreiecksbeziehung zwischen Sierpinski, Pascal und Lucas", die wir - aus Zeitgründen - leider nicht genauer erkunden konnten.