Sierpinski Dreieck
-
Hi
Ich habe mal 2 Fragen dazu, und zwar
1.) Stimmt es, dass man das S. Dreieck nur durch Rekursion bewerkstelligen kann (also nicht iterativ) ?
2.) Kann mir jemand einen Link zu einem Tut geben, in dem das Sierpinsky Dreick anhand von C++ (oder Object Pascal) erklärt wird ?
-
1. Meinst du ohne rekursiven Prozess oder ohne rekursive Implementierung? Man kann jeden rekursiven Prozess iterativ implementieren und jeden iterativen Prozess rekursiv implementieren.
-
Öhm jetzt hast du mich verwirrt
Was meinst du mit rekursiver Implementierung bzw Prozess?
Mein Wissen war halt bis jetzt, dass man jedes rekursive Verfahren auch mit einem iterativen bewerkstelligen kann. Und vor kurzem habe ich von jemandem gehört, dass das mit dem Sierpinsky Dreieck nicht der Fall ist
-
Rekursive Implementierung: Eine Funktion, die sich selbst aufruft.
Rekursiver Prozess: Eine Berechnung, in deren Verlauf noch zu erledigende Zwischenberechnungen auf einem Stapel abgelegt werden (die Definition ist möglicherweise nicht ganz wasserdicht)Offensichtlich bietet sich für rekursive Prozesse eine rekursive Implementation an, da man dabei implizit einen Stack, auf dem die ganzen Activationrecords abgelegt werden, hat. Man kann aber natürlich auch auf Selbstaufrufe verzichten, und per Hand einen Stack verwalten.
Andererseits kann man auch iterative Prozesse durch rekursive Funktionen beschreiben. Das setzt allerdings in der Praxis einen Compiler voraus, der Endrekursion automatisch eliminieren kann.
Kannst auch mal das lesen, wenn du nicht gegen Scheme allergisch bist
http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2Was das jetzt mit dem Sierpinski-Dreieck zu tun hat? Ich weiß jetzt leider nicht mehr ganz genau was das war, nur ungefähr, aber es kann gut sein, dass das gute Stück nicht mit einem iterativen Prozess herstellbar ist ... das kann man wenn man lustig ist sicherlich irgendwie beweisen.
Was die Implementation angeht, gibt es wie gesagt entweder die Möglichkeit, eine rekursive Funktion zu schreiben, oder einen expliziten Stack zu verwenden.
-
Da das Sierpinski-Dreieck eine fraktale Zeichnung ist, bietet sich natürlich eine rekursive Implementation an. Du kannst allerdings auch iterativ dieses Dreieck darstellen. Allerdings wird es dann erstens schwieriger eine variable Tiefe (Anzahl der Dreiecke im Dreieck) anzugeben und zweitens kommt das wohl nicht gerade dem eigentlichen Gedanken dieser fraktalen Darstellung nahe. Rekursiv läßt sich das ganze einfach eleganter, schneller und anpassungsfähiger Umsetzen.
-
Ich weiß zwar auch nicht mehr genau was das Sirpinski-Dreieck war, aber ich bin mir sicher, daß man es auch iterativ berechnen kann.
Denn jede rek. berechenbare Funktion ist z.B. goto oder while-berechenbar.
Bzw. wer das mehr liebt: Turing-berechenbar.Es gibt da in der Berechenbarkeits-Theorie den Rekursionssatz, der sagt genau das aus. Einen Beweis oder eine genauere Formulierung krieg ich aus dem Kopf aber nicht zusammen. Die benötigten formalen Hilfsmittel waren auch nicht zu verachten...
MfG Jester
-
Für alle die es nicht kennen (Sierpinski-Dreieck)
:. * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
-
Gegeben sind drei Eckpunkte A,B,C eines Dreiecks.
Man beginne bei einem beliebigen Punkt X und wähle zufällig einen der Eckpunkte aus. Genau in der Mitte zwischen X und dem gewählten Eckpunkt zeichnet man einen Punkt P. Nun sucht man wieder rein zufällig einen der Eckpunkte aus und zeichnet wieder auf halber Strecke zwischen gewähltem Punkt und P einen neuen Punkt P'.Mach das einige Tausend mal und du bekommst ein Sierpinski Dreieck.