Einstieg - Eine selbstähnliche Figur
Ein Baum mit Verästelung
Betrachte den (idealisiert dargestellten) Baum in der folgenden Abbildung.
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.
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:
...
