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.
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)
Hinweis zu Aufgabe b)
g nacheinander annimmt.Hinweis zu Aufgabe c)
Hinweis zu Aufgabe d)
Erwartungshorizont
Erwartungshorizont zu Aufgabe a)
Höchster Stand (unten der erste Aufruf):
| Ebene | Aufruf | Zustand | Rückgabe |
|---|---|---|---|
| 4 (oben) | vorfahren(0) | Abbruch | 0 |
| 3 | vorfahren(1) | wartet auf 2 + 2 · vorfahren(0) | 2 |
| 2 | vorfahren(2) | wartet auf 2 + 2 · vorfahren(1) | 6 |
| 1 (unten) | vorfahren(3) | wartet auf 2 + 2 · vorfahren(2) | 14 |
Rückgabewert von vorfahren(3): 14 (2 + 4 + 8).
Erwartungshorizont zu Aufgabe b)
Die Aufrufe laufen mit \(g, g-1, \dots, 0\): Rekursionstiefe \(g + 1\), Anzahl der Aufrufe ebenfalls \(g + 1\) (lineare Rekursion).
Erwartungshorizont zu Aufgabe c)
Sieben Aufrufe; Rückgabewerte 0 (Blätter), 2 + 0 + 0 = 2 und 2 + 2 + 2 = 6.
Erwartungshorizont zu Aufgabe d)
\(C(g) = 1 + 2\,C(g-1)\), \(C(0) = 1\): \(C(1) = 3\), \(C(2) = 7\), \(C(3) = 15\), allgemein \(C(g) = 2^{g+1} - 1\). Beide Methoden liefern dieselben Werte und haben dieselbe Rekursionstiefe \(g + 1\). vorfahren2 berechnet aber das Teilergebnis vorfahren2(g - 1) doppelt; die Zahl der Aufrufe wächst exponentiell statt linear. Für 30 Generationen sind es über zwei Milliarden Aufrufe statt 31 — die Methode des Kollegen ist ungeeignet.
Die Türme von Hanoi
AFB II–IIIBeim Spiel „Türme von Hanoi“ liegen \(n\) unterschiedlich große Scheiben auf Stab A, die größte unten. Sie sollen auf Stab C umgesetzt werden; Stab B dient als Hilfe. Es darf immer nur die oberste Scheibe eines Stabes bewegt werden, und nie darf eine größere auf einer kleineren liegen. Die Methode hanoi gibt die nötigen Züge aus.
static void hanoi(int n, char von, char hilf, char nach) {
if (n == 0) {
return;
}
hanoi(n - 1, von, nach, hilf);
System.out.println(von + " -> " + nach);
hanoi(n - 1, hilf, von, nach);
}- Analysieren Sie den Aufruf
hanoi(2, 'A', 'B', 'C'): Zeichnen Sie den Aufrufbaum und geben Sie die Ausgabe an. 5 BE - Begründen Sie, dass
hanoifür jedes \(n \ge 0\) terminiert. 2 BE - Leiten Sie her, dass
hanoi(n, …)genau \(2^n - 1\) Züge ausgibt. 4 BE - Beurteilen Sie nach einer Legende die Aufgabe von Mönchen, 64 Scheiben mit einem Zug pro Sekunde umzusetzen: Scheitert das Vorhaben am Aufrufstapel oder an der Zeit? 4 BE
Insgesamt 15 BE
Hinweise
Hinweis zu Aufgabe a)
nach und hilf, der zweite die von von und hilf. Die Ausgabe steht zwischen den beiden Aufrufen.Hinweis zu Aufgabe b)
Hinweis zu Aufgabe c)
Hinweis zu Aufgabe d)
Erwartungshorizont
Erwartungshorizont zu Aufgabe a)
Aufrufbaum: hanoi(2,A,B,C) ruft hanoi(1,A,C,B) und hanoi(1,B,A,C) auf; jeder davon ruft zweimal hanoi(0,…) auf, die sofort zurückkehren (7 Aufrufe).
hanoi(1,A,C,B) gibt A -> B aus, danach hanoi(2,…) selbst A -> C, danach hanoi(1,B,A,C) B -> C. Ausgabe:
A -> B A -> C B -> C
Erwartungshorizont zu Aufgabe b)
Jeder Selbstaufruf verkleinert \(n\) um 1. Von \(n \ge 0\) aus wird deshalb nach \(n\) Stufen \(n = 0\) erreicht, wo die Methode ohne Selbstaufruf endet. Da jeder Aufruf höchstens zwei weitere erzeugt, ist die Gesamtzahl der Aufrufe endlich.
Erwartungshorizont zu Aufgabe c)
\(Z(0) = 0\), \(Z(n) = 2\,Z(n-1) + 1\). Daraus: \(Z(1) = 1\), \(Z(2) = 3\), \(Z(3) = 7\). Gilt \(Z(n-1) = 2^{n-1} - 1\), so folgt \(Z(n) = 2(2^{n-1} - 1) + 1 = 2^n - 1\). Mit \(Z(0) = 2^0 - 1 = 0\) gilt die Formel für alle \(n \ge 0\).
Erwartungshorizont zu Aufgabe d)
Die Rekursionstiefe beträgt nur \(65\) (n = 64 bis 0) — der Aufrufstapel ist kein Problem. Die Zahl der Züge ist aber \(2^{64} - 1 \approx 1{,}8 \cdot 10^{19}\). Bei einem Zug pro Sekunde dauert das etwa \(1{,}8 \cdot 10^{19} : (3{,}16 \cdot 10^{7}) \approx 5{,}8 \cdot 10^{11}\) Jahre, rund das Vierzigfache des Alters des Universums. Das Vorhaben scheitert an der Zeit, nicht am Speicher; auch ein Computer mit einer Milliarde Züge pro Sekunde bräuchte fast 600 Jahre.