Aufgabenblock — AFB III
Begründen statt nur ausführen: Behauptungen widerlegen, rekursive Methoden entwerfen und implementieren, Verfahren beurteilen, Fehler finden und Aussagen allgemein zeigen. Jede Aufgabe hat ein prüfbares Kernergebnis — formuliere die Begründung trotzdem in ganzen Sätzen, bevor du die Musterlösung aufklappst.
Tom behauptet: „Mergesort braucht für \(n\) Elemente immer genau \(n\cdot\log_2 n\) Vergleiche.“ Widerlegen Sie die Behauptung mit der bereits sortierten Reihung 1, 2, …, 8.
Geben Sie für Ihr Gegenbeispiel die tatsächliche Anzahl der Vergleiche an.
Musterlösung anzeigen
Musterlösung: Für \(n = 8\) wäre \(n\log_2 n = 24\). Bei der sortierten Reihung ist beim Mischen jedes linke Element kleiner als jedes rechte; es werden nur die Elemente der linken Hälfte verglichen, der Rest der rechten wird ohne Vergleich angehängt. Ebene 1: \(4\cdot1\), Ebene 2: \(2\cdot2\), Ebene 3: \(1\cdot4\) — zusammen 12 Vergleiche.
Die Behauptung ist widerlegt. Richtig ist: \(n\log_2 n\) ist eine obere Schranke; der ungünstigste Fall liegt bei \(n\log_2 n - n + 1 = 17\), der günstigste bei \(\frac{n}{2}\log_2 n = 12\).
Die Potenz \(x^n\) soll nach Teile und herrsche berechnet werden: \(x^n = x^{n/2}\cdot x^{n/2}\) für gerades \(n\), \(x^n = x^{(n-1)/2}\cdot x^{(n-1)/2}\cdot x\) für ungerades \(n\), \(x^0 = 1\). Entwerfen Sie eine rekursive Methode static long potenz(long x, int n), die jedes Teilergebnis nur einmal berechnet.
Geben Sie an, wie viele Multiplikationen Ihre Methode für \(n = 1000\) ausführt.
potenz(x, n / 2) * potenz(x, n / 2) würden dieselbe Arbeit doppelt machen.Musterlösung anzeigen
Musterlösung:
static long potenz(long x, int n) {
if (n == 0) {
return 1;
}
long h = potenz(x, n / 2);
if (n % 2 == 0) {
return h * h;
}
return h * h * x;
}Exponenten der Aufrufkette: 1000, 500, 250 (gerade, je 1), 125 (ungerade, 2), 62 (1), 31, 15, 7, 3, 1 (ungerade, je 2), 0 (keine). Summe \(1 + 1 + 1 + 2 + 1 + 2 + 2 + 2 + 2 + 2 = \) 16 Multiplikationen statt 999 — höchstens \(2(\lfloor\log_2 n\rfloor + 1)\).
Eine App soll fib(40) mit der baumrekursiven Methode aus dem Unterricht berechnen. Für die Anzahl der Aufrufe gilt \(A(n) = 2\,\text{fib}(n+1) - 1\), und es ist \(\text{fib}(41) = 165\,580\,141\). Beurteilen Sie diesen Ansatz im Vergleich zur iterativen Fassung.
Geben Sie die Anzahl der Aufrufe in Millionen an (auf eine Nachkommastelle).
Musterlösung anzeigen
Musterlösung: \(A(40) = 2\cdot165\,580\,141 - 1 = 331\,160\,281\approx\) 331,2 Mio. Aufrufe. Dieselben Teilprobleme werden immer wieder neu berechnet (z. B. fib(38) zweimal, fib(37) dreimal …), der Aufwand wächst exponentiell. Die Rekursionstiefe ist mit 40 dagegen harmlos.
Die iterative Fassung braucht 40 Schleifendurchläufe. Urteil: Der baumrekursive Ansatz ist für die App ungeeignet — die Rekursion ist hier kein Teile und herrsche, weil sich die Teilprobleme überschneiden.