Logo des digitalen Schulbuchs inf-schule.de. Schriftzug in Zustandsübergangsdiagramm eines endlichen Automaten.

Einstieg - Eine selbstähnliche Figur

Ein Baum mit Verästelung

Betrachte den (idealisiert dargestellten) Baum in der folgenden Abbildung.

Baum

Welche Regelmäßigkeit ist hier zu erkennen?

Aufgabe 1

Die folgende Abbildung zeigt eine Zerlegung des Baumes in Teile, die dem gesamten Baum ähnlich sind.

Zerlegung des Baums

Wie könnte man diese Zerlegung weiter fortsetzen?

Aufgabe 2

Wie zeichnet man einen Baum mit der Stammlänge 200? Der folgende Lösungsansatz benutzt eine rekursive Problemreduktion.

zeichne_Baum(200):
    gehe_vorwaerts(200)
    drehe_dich_nach_rechts(45)
    zeichne_Baum(100)
    drehe_dich_nach_links(90)
    zeichne_Baum(100)
    drehe_dich_nach_rechts(45)
    gehe_rueckwaerts(200) 

(a) Mach dir klar, wie dieser Lösungsansatz funktioniert.

(b) Warum handelt es sich um einen Ansatz mit rekursiver Problemreduktion?

Aufgabe 3

Die in Aufgabe 2 gezeigte rekursive Problemreduktion soll zu einem rekursiven Algorithmus verallgemeinert werden. Ergänze die fehlenden Anweisungen.

ALGORITHMUS zeichne_Baum(stamm):
    wenn stamm >= 2:
        ...
X

Fehler melden

X

Suche