FRage zu Rekursion vs. Iteration
dirk raecke
es heißt ja immer, dass rekursive Algorithmen sich auch meist (immer?) iterativ lösen lassen.
Ist jemandem von Euch ein echt iterativer Algorithmus zum Zeichnend es Sierpinskidreiecks bekannt?
Ich meine nicht über Zufallszahlen!
Danke
Dirk
Ewgenij Starostin
> Ist jemandem von Euch ein echt iterativer Algorithmus zum Zeichnend es
> Sierpinskidreiecks bekannt?
Wenn es nur ums Zeichnen geht und auf die Gefahr hin, etwas übersehen zu
haben, ...
Das Dreieck hat die Eigenschaft, dass an jedem neu gezeichneten Dreieck
drei Dreiecke der nächsten Iteration zu zeichnen sind, die bei jeweils
einem Eckpunkt mit jeweils einem Mittelpunkt einer Seite des Dreiecks
verbunden sind. (Jedenfalls würde ich es so zeichnen.)
seitel = liste /* linke Mittelpunkte */
seiter = liste /* rechte Mittelpunkte */
seiteo = liste /* obere Mittelpunkte */
zeichne( umriss, bei (0, 0) )
seiteo.push( mittelpunkt( untere seite( umriss ) ) )
für i ab 0 bis iterationsmaximum oder unendlich
seitel2 = seitel;
seiter2 = seiter;
seiteo2 = seiteo;
solange seitel nicht leer
t = dreieck für iteration i
zeichne( t, mit rechtem eckpunkt( t ) bei seitel.pop )
seitel2.push( mittelpunkt( linke seite( t ) ) )
seiter2.push( mittelpunkt( rechte seite( t ) ) )
seiteo2.push( mittelpunkt( obere seite( t ) ) )
fertig
solange seiter nicht leer
t = dreieck für iteration i
zeichne( t, mit linkem eckpunkt( t ) bei seiter.pop )
seitel2.push( mittelpunkt( linke seite( t ) ) )
seiter2.push( mittelpunkt( rechte seite( t ) ) )
seiteo2.push( mittelpunkt( obere seite( t ) ) )
fertig
solange seiteo nicht leer
t = dreieck für iteration i
zeichne( t, mit unterem eckpunkt( t ) bei seiteo.pop )
seitel2.push( mittelpunkt( linke seite( t ) ) )
seiter2.push( mittelpunkt( rechte seite( t ) ) )
seiteo2.push( mittelpunkt( obere seite( t ) ) )
fertig
seitel = seitel2;
seiter = seiter2;
seiteo = seiteo2;
fertig
zeichne() macht dabei nicht nur die Grafik, sondern legt auch irgendwie
die geometrischen Daten für die Objekte fest.
Wenig erklärende Skizze:
seiteo ___
\
_____o_____
\ /
\ /
seitel ---o o--- seiter
\ /
\ /
V
> Ich meine nicht über Zufallszahlen!
Also eigentlich sieht das Dreieck gar nicht so zufällig aus :)
HTH
--
Kind regards
Ewgenij Starostin, es...@cs.tu-berlin.de
You can find stuff which I would otherwise put in this signature here:
http://user.cs.tu-berlin.de/~estar/sig.cgi (still under construction)
Ewgenij Starostin
> seitel2 = seitel;
> seiter2 = seiter;
> seiteo2 = seiteo;
Ups. Es funktioniert besser, wenn man statt dessen
seitel2 = liste
seiter2 = liste
seiteo2 = liste
macht.
Demo: http://user.cs.tu-berlin.de/~estar/sierpinski.cgi
Andere Anzahl Iterationen (z. B. 3):
http://user.cs.tu-berlin.de/~estar/sierpinski.cgi?iterations=3
Quellcode: http://user.cs.tu-berlin.de/~estar/sierpinski.cgi?source
(Für die ersten beiden URLs sollte man einen Client benutzen, der PNG
kann.)
dirk raecke
vielen Dank erstmal.
Guck mir den Code mal durch.
Aber es sieht aus, wie es sich meien Schüler prinzipiell gedacht haben - jedenfalls auf den ersten Blick. Du killst also die
MItte. Ich denke mit dem Ansatz sollte es vielleicht auch gelingen, das Ding zu zeichenn, also nur die Randlinien der Dreiecke zu
erzeuigen?
Mal sehen...
Jedenfaklls besten Dank und ich hoffe, du hast das ganze ding nicht extra wegen der frage geschrieben .....
Dirk
"Ewgenij Starostin" <es...@cs.tu-berlin.de> schrieb im Newsbeitrag news:d803qv$nte$1...@news.cs.tu-berlin.de...
dirk raecke
ich meine, dass man zufällig die intervalle halbiert und das dreieck sozusagen aus zufallspunkten zusammenbaut...geht ganz gut ab
iterationen um die 20000
hier aus nem delphibeispiel zusammengeackert....:
var i,j,p,palt : integer;
anzahl: longint;
x: array[1..3] of integer;
y: array[1..3] of integer;
ya,xa:integer;
begin
for i:=0 to image1.width do
for j:=0 to image1.height do
image1.Canvas.pixels[i,j]:=clwhite;
x[1]:=200;y[1]:=0;
x[2]:=400;y[2]:=400;
x[3]:=0;y[3]:=400;
anzahl:=strtoint(edit1.text) ;
randomize;
p:=random(3)+1;
xa:=x[p];ya:=y[p];
for i:=1 to anzahl do
begin
p:=random(3)+1;
xa:=(xa+x[p]) DIV 2;
ya:=(ya+y[p]) DIV 2;
image1.Canvas.Pixels[xa,ya]:=0;
end;
end;
Ewgenij Starostin
> Aber es sieht aus, wie es sich meien Schüler prinzipiell gedacht haben
> - jedenfalls auf den ersten Blick. Du killst also die MItte.
Ja. Das ist der direkteste Weg (und außerdem die direkte Umwandlung des
rekursiven Algorithmus).
> Ich denke mit dem Ansatz sollte es vielleicht auch gelingen, das Ding
> zu zeichenn, also nur die Randlinien der Dreiecke zu erzeuigen?
Natürlich. (Im Quellcode ersetzt man z. B. imagefilledpolygon durch
imagepolygon.)
> ich hoffe, du hast das ganze ding nicht extra wegen der frage
> geschrieben .....
Doch, und zwar weil ich die Frage interessant fand ;)
Ewgenij Starostin
> achso nochmal zu den zufallszahlen.
>
> ich meine, dass man zufällig die intervalle halbiert und das dreieck
> sozusagen aus zufallspunkten zusammenbaut...geht ganz gut ab
> iterationen um die 20000
Cool. Die Möglichkeit ist mir zuvor nicht aufgefallen.
> hier aus nem delphibeispiel zusammengeackert....:
Danke.