Rekursionsfunktion verstehen |
| 09.07.2016, 20:13 | Auf diesen Beitrag antworten » |
| Vanni0601 | Rekursionsfunktion verstehen Hallo Zusammen, Ich bin zur Zeit am Lernen für meine Algorithmen-Klausur in 2 Wochen. Das Thema Rekursion habe ich immer fleißig vor mir hergeschoben, doch nun muss ich da langsam mal ran. Und zwar ist mir diese Rekursionssache vollkommen unklar. Wenn mir eine Rekursionsgleichung gegeben ist, weiß ich nicht wirklich wie ich diese interpretieren soll und was diese genau aussagt. Ein weiteres Problem stellt sich mir, wenn ein bestimmtes Problem geschildert wie ich daraus eine Rekursionsfunktion erstellen soll. Zum Beispiel habe ich folgende Aufgabe vor mir liegen: Betrachten Sie die Baumstruktur: innere Knoten haben eine von zwei möglichen Farben: Pink und lila. Ein pinker Knoten hat genau 2 lila Kinder. Ein lila Knoten hat genau 2 Pinke Kinder. Blätter haben keine Farbe. Die Wurzel ist lila. Geben Sie eine rekursionsgleichung für die Anzahl der Knoten in Abhängigkeit von der Tiefe n des Baumes an. Finden Sie eine geschlossene Form der Rekursionsgleichung und beweisen Sie deren Korrektheit. So, wie der Baum aussieht habe ich mir bereits aufgezeichnet und was prinzipiell mit der Anzahl der Knoten in jedem weiteren Level des Baumes passiert ist mir auch klar. Aber wie zum Teufel stelle ich darauf aufbauend eine Rekursionsgleichung auf? Ich bin echt verzweifelt, wahrscheinlich brauche ich nur einen kleinen Anschubser, aber ich verstehe momentan die ganze Geschichte mit den Rekursionen nicht. Ich bin dankbar für jede noch so kleine Hilfe. Grüße Vanny 
|
|
|
|
| 09.07.2016, 21:33 | Auf diesen Beitrag antworten » |
| eulerscheZahl | Nehmen wir an, wir sind in Reihe m (nicht die unterste Reihe, wird also noch gefärbt). Außerdem sei m ungerade (also wird lila gefärbt, wenn wir die Wurzel als Reihe 1 sehen) und größer 1. Die Zahl der lila Knoten ist dann die Anzahl der Knoten in der aktuellen Reihe plus der Anzahl in allen Reihen darüber. Für die aktuelle Reihe sind das 2^m Knoten lilaKnoten(1) = 1 //Wurzelknoten lilaknoten(m) = 2^m + lilaKnoten(m-2) //aktuelle Reihe + alle vorherigen |
| 08.04.2017, 09:28 | Auf diesen Beitrag antworten » |
| skubidoo09 | RE: Rekursionsfunktion verstehen Warum zählt man die lilaKnoten nicht? |
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|