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 Spinne

  void 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 vor

  void 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 Sierpinski

  public void paint (Graphics g) {
    silke = new Spinne(this, 200, 300, -30);
    zeichneDreieck(tiefe, 90);
    } // Ende paint

  void 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 Dreieck

  static 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.