Dein Fortschritt:
0 / 0 Aufgaben
1
Vorfahren im Stammbaum
AFB I–IIEin Ahnenforschungsprogramm berechnet, wie viele Vorfahren eine Person in den letzten g Generationen höchstens hat: 2 Eltern, 4 Großeltern, 8 Urgroßeltern usw. Dazu gibt es zwei Methoden. Die zweite hat ein Kollege geschrieben.
Material: zwei Methoden
static int vorfahren(int g) {
if (g == 0) {
return 0;
}
return 2 + 2 * vorfahren(g - 1);
}static int vorfahren2(int g) {
if (g == 0) {
return 0;
}
return 2 + vorfahren2(g - 1) + vorfahren2(g - 1);
}- Stellen Sie den Aufrufstapel zu
vorfahren(3)in dem Moment dar, in dem er am höchsten ist, und geben Sie die Rückgabewerte aller Aufrufe an. 4 BE - Geben Sie für
vorfahren(g)die Rekursionstiefe und die Anzahl der Aufrufe in Abhängigkeit von \(g\) an. 2 BE - Zeichnen Sie den Aufrufbaum für
vorfahren2(2)mit den Rückgabewerten. 4 BE - Leiten Sie eine Formel für die Anzahl der Aufrufe von
vorfahren2(g)her und vergleichen Sie beide Methoden. 5 BE
Insgesamt 15 BE
Hinweise
Hinweis zu Aufgabe a)
Beim höchsten Stand liegt der Aufruf mit der Abbruchbedingung oben.
Hinweis zu Aufgabe b)
Zählen Sie die Werte, die
g nacheinander annimmt.Hinweis zu Aufgabe c)
Jeder Aufruf mit \(g \ge 1\) hat zwei Kinder mit \(g - 1\).
Hinweis zu Aufgabe d)
Stellen Sie eine Gleichung \(C(g) = 1 + 2\,C(g-1)\) mit \(C(0) = 1\) auf und setzen Sie einige Werte ein.