• Rekursion
  • CSchunck
  • 30.06.2020
  • Allgemeine Hochschulreife
  • Informatik
  • 11
Um die Lizenzinformationen zu sehen, klicken Sie bitte den gewünschten Inhalt an.

Re­kur­si­on ist neben der Ite­ra­ti­on das mäch­tigs­te Werk­zeug der Pro­gram­mie­rung. Jedes denk­ba­re Pro­gramm kann le­dig­lich durch Zu­wei­sun­gen, Ver­zwei­gun­gen und Re­kur­si­o­nen (oder Ite­ra­ti­o­nen oder Sprün­ge) pro­gram­miert wer­den. Bevor wir uns der Re­kur­si­on zu­wen­den, be­trach­ten wir selbst­ähn­li­che Fi­gu­ren: Frak­ta­le.

Frak­tal

Ein Frak­tal ist eine (geo­me­tri­sche) Figur, die aus einem Teil be­steht, der zu der ge­sam­ten Figur ähn­lich ist. Eine sol­che Figur muss zwangs­wei­se un­end­lich sein, wir kön­nen sie nur an­nä­hern. Ein ein­fa­ches Bei­spiel ist das Sierpinsky-​Dreieck.

1
Sie be­nö­ti­gen ein lee­res Blatt in DIN-A4-​Größe, einen Blei­stift und ein Li­ne­al.
  • Zeich­nen Sie ein be­lie­bi­ges Drei­eck. Die Sei­ten­län­gen soll­ten ca. 10-15cm be­tra­gen.
  • Mar­kie­ren Sie die Mit­ten der Sei­ten und ver­bin­den Sie je­weils zwei Sei­ten­mit­ten mit­ein­an­der durch eine Stre­cke. Es ent­ste­hen so 4 Teil­drei­ecke.
  • Wie­der­ho­len Sie den zwei­ten Schritt mit den drei äu­ße­ren Teil­drei­ecken
gleich­sei­ti­ges Sierpinsky-​Dreieck

Führt man die­ses Ver­fah­ren end­los fort, so ent­steht als Grenz­fi­gur das so ge­nann­te Sierpinsky-​Dreieck. Dabei ist jedes Teil­drei­eck zum ge­sam­ten Drei­eck ähn­lich.

Das erste ge­zeich­ne­te Drei­eck nennt man In­iti­a­tor. Er be­schreibt das „in­iti­a­le“ (erste) Ob­jekt. Die Bil­dungs­re­geln 2 und 3 hei­ßen Ge­ne­ra­tor. Sie geben an, wie neue Drei­ecke „ge­ne­riert“ wer­den. Das fol­gen­de Ar­beits­blatt be­glei­tet die Um­set­zung eines Pro­gramms zur Er­stel­lung von Sierpinsky-​Dreiecken.

Zeich­nen mit Del­phi

In jedem For­mu­lar in Del­phi ist ein (ganz­zah­li­ges) Ko­or­di­na­ten­sys­tem ein­ge­bet­tet. Der Ur­sprung ist der Punkt links oben. Die x-​Achse ver­läuft, wie üb­lich, von links nach rechts. Die y-​Achse da­ge­gen wächst von oben nach unten. Jedem Punkt auf dem For­mu­lar ist daher ein Paar ganz­zah­lig po­si­ti­ver Ko­or­di­na­ten zu­ge­ord­net. Die Ein­heit, in der die Ko­or­di­na­ten­wer­te an­ge­ge­ben sind, ist die An­zahl der Pixel, die der Punkt in waa­ge­rech­ter oder senk­rech­ter Ent­fer­nung vom Ur­sprung liegt.

Be­we­gen des Cur­sors

Die Flä­che, auf der wir zeich­nen, heißt Can­vas (Lein­wand) und ist ein At­tri­but des For­mu­lars. Um den (un­sicht­ba­ren) Zei­chen­cur­sor (ohne zu zeich­nen) an eine be­stimm­te Po­si­ti­on zu brin­gen, kön­nen wir die Ope­ra­ti­on Mo­ve­To ver­wen­den.

Bei­spiel: Form1.can­vas.Mo­ve­To(23, 117);

Der Be­fehl be­wegt den Zei­chen­cur­sor an den Punkt (23|117).

Zeich­nen einer Stre­cke

Die Ope­ra­ti­on Li­ne­To zeich­net eine Stre­cke vom ak­tu­el­len Punkt des Zei­chen­cur­sors zu den Ziel­ko­or­di­na­ten. Bei­spiel: Form1.can­vas.Li­ne­To(47,11);

Der Be­fehl zeich­net eine Linie von der ak­tu­el­len Po­si­ti­on P zum Punkt (47|11).

2
(Vor­be­rei­ten­de Auf­ga­be)
Schrei­ben Sie ein Pro­gramm, das eine Stre­cke zwi­schen zwei vom Be­nut­zer ein­ge­ge­be­nen Punk­ten zeich­net. Die Ein­ga­be der Ko­or­di­na­ten er­folgt für jeden Punkt durch An­ga­be der x- und der y-​Koordinate in je einer Edit­kom­po­nen­te.
Da­ten­typ TPoint

type TPoint = re­cord x : in­te­ger; y : in­te­ger;end;

3
Schrei­ben Sie eine Pro­ze­dur Zeich­ne­Stre­cke, die eine Stre­cke zwi­schen zwei Punk­ten zeich­net. Ver­wen­den Sie den vor­ge­fer­tig­ten Da­ten­typ TPoint. Tes­ten Sie ihre Pro­ze­dur.
Pro­ce­du­re Zeich­ne­Stre­cke(A,B: TPoint);
4
Zeich­nen des Drei­ecks
  • Der Be­nut­zer gibt die Ko­or­di­na­ten drei­er ver­schie­de­ner Punk­te A,B,C ein. Die Punk­te sol­len nicht auf einer Linie lie­gen. Das Pro­gramm zeich­net dann das Drei­eck ΔABC.
  • Über­le­gen Sie sich mög­li­che Feh­ler, die dem Be­nut­zer bei der Ein­ga­be der Punk­te un­ter­lau­fen könn­ten. No­tie­ren Sie Bei­spie­le und Lö­sungs­mög­lich­kei­ten.
  • Fal­sche oder un­sin­ni­ge Ein­ga­ben sol­len ab­ge­fan­gen wer­den. Der Be­nut­zer er­hält eine mög­lichst gute Feh­ler­mel­dung per showmessage-​Befehl und die Werte wer­den auf einen Stan­dard­fall ge­setzt.

Da Frak­ta­le je­weils nur geo­me­tri­sche Grenz­wer­te dar­stel­len, kön­nen wir sie nur durch end­lich viele Schrit­te an­nä­hern. Ein Schritt be­deu­tet, dass der Ge­ne­ra­tor ein­mal aus­ge­führt wird. Unser Ziel ist nun, ein Pro­gramm zu schrei­ben, wel­ches das Sierpinsky-​Dreieck durch eine vom Be­nut­zer ein­ge­ge­be­ne Zahl von Schrit­ten an­nä­hert.

Re­chen­weg

Die Ko­or­di­na­ten des Mit­tel­punk­tes M sind die Ko­or­di­na­ten des (ge­run­de­ten) arith­me­ti­schen Mit­tels der Ko­or­di­na­ten der Punk­te A und B.

M.x=(A.x+B.x)/2

M.y=(A.y+B.y)/2.

5
Schrei­ben Sie eine Funk­ti­on
Mit­tel­punkt: TPoint × TPoint → TPoint,
die den Mit­tel­punkt der Stre­cke zwi­schen zwei Punk­ten be­rech­net.
6
Sor­tie­ren Sie die Ar­beits­schrit­te nach Ihrer Rei­hen­fol­ge!
(1-5)
  • 3
    Be­rech­ne die Mit­tel­punk­te der drei Sei­ten.
  • 5
    Führe den Gen­ra­tor mit den äu­ße­ren drei Teil­drei­ecken aus.
  • 4
    Ver­rin­ge­re die Schritt­zahl k um eins.
  • 2
    Prüfe, ob die Zahl der noch aus­zu­füh­ren­den Schrit­te k grö­ßer als null ist. Falls nein, be­en­de das Zeich­nen.
  • 1
    Zeich­ne das Drei­eck.
7
Schrei­ben Sie eine Pro­ze­dur Ge­ne­ra­tor. Die Pro­ze­dur ar­bei­tet die Schrit­te aus Auf­ga­be 6 nach­ein­an­der ab. Ver­wen­den Sie fol­gen­de Si­gna­tur:
Pro­ce­du­re Ge­ne­ra­tor(k: in­te­ger; A,B,C : TPoint);
x