Aufgabenblock — AFB II
Zehn Aufgaben aus allen Unterkapiteln: Methoden analysieren, Ausgaben beim Ab- und Aufstieg ermitteln, Rekursion und Iteration vergleichen, Vergleichszahlen herleiten — mit gestuften Tipps, wenn du nicht weiterkommst.
static int m(int a, int b) {
if (b == 0) {
return a;
}
return m(b, a % b);
}Analysieren Sie den Aufruf m(84, 36): Geben Sie den Rückgabewert und die Anzahl der Aufrufe an und nennen Sie, was die Methode berechnet.
(a, b) wird (b, a % b).Vollständige Lösung
m(84, 36) → m(36, 12) → m(12, 0). Der dritte Aufruf erfüllt die Abbruchbedingung und liefert 12; der Wert wird unverändert nach oben durchgereicht. Die Methode berechnet den größten gemeinsamen Teiler nach dem euklidischen Algorithmus. Weil der Selbstaufruf die letzte Aktion ist (return m(…)), ist sie endrekursiv und lässt sich direkt als Schleife schreiben.static void p(int n) {
if (n > 0) {
System.out.print(n);
p(n - 1);
System.out.print(n);
}
}Ermitteln Sie die vollständige Ausgabe des Aufrufs p(3).
p(0) macht nichts; beim Aufstieg folgen 1, 2, 3.Vollständige Lösung
321. p(0) erfüllt die Bedingung n > 0 nicht und kehrt sofort zurück. Beim Aufstieg setzt jeder wartende Aufruf hinter dem Selbstaufruf fort — der zuletzt begonnene zuerst: 123. Gesamt: 321123. Anweisungen nach dem Selbstaufruf laufen also in umgekehrter Reihenfolge.static int f(int n) {
if (n == 0) {
return 0;
}
return 1 + f(n - 2);
}Untersuchen Sie die Methode: Geben Sie f(10) und die Anzahl der Aufrufe an. Für welche Eingaben endet die Rekursion nicht?
Vollständige Lösung
f(10) = 1 + 1 + 1 + 1 + 1 + 0 = 5 nach 6 Aufrufen. Für ungerade n wird die 0 übersprungen (…, 3, 1, −1, −3, …): Die Abbruchbedingung wird nie erreicht, die Aufrufe laufen bis zum StackOverflowError. Dasselbe gilt für negative n. Abhilfe: Abbruch bei n <= 0 oder die Voraussetzung „n gerade und ≥ 0“ festlegen.Die Summe einer Reihung wird einmal mit einer Schleife und einmal rekursiv berechnet:
static int summe(int[] a, int i) {
if (i == a.length) {
return 0;
}
return a[i] + summe(a, i + 1);
}Vergleichen Sie beide Fassungen für eine Reihung mit 6 Elementen und dem Startaufruf summe(a, 0): Wie viele Aufrufe braucht die rekursive, wie viele Schleifendurchläufe die iterative Fassung?
i == a.length zählt mit, obwohl er kein Element mehr addiert.Vollständige Lösung
i = 0 bis 6, also 7, alle gleichzeitig offen (Tiefe 7). Iterativ: 6 Durchläufe in einem einzigen Methodenaufruf. Die Zahl der Additionen ist gleich; die rekursive Fassung braucht aber je Element einen Rahmen auf dem Aufrufstapel. Umformung: Schleifenvariable → Parameter i, verneinte Schleifenbedingung → Abbruchbedingung i == a.length.static String umkehren(String s) {
if (s.length() <= 1) {
return s;
}
return umkehren(s.substring(1)) + s.charAt(0);
}Stellen Sie die Aufrufkette von umkehren("Regal") mit den Rückgabewerten dar und geben Sie das Ergebnis ein.
Vollständige Lösung
umkehren("Regal") → umkehren("egal") → umkehren("gal") → umkehren("al") → umkehren("l") = "l". Aufstieg: "la", "lag", "lage", "lageR". Ergebnis lageR — das große R steht jetzt hinten, Groß- und Kleinschreibung bleiben erhalten.Die rekursive binäre Suche aus dem Unterricht (Abbruch ohne Treffer bei links > rechts, sonst ein Blick auf a[mitte] und höchstens ein Selbstaufruf) wird auf eine sortierte Reihung mit 100 Elementen angewendet. Leiten Sie her, wie viele Aufrufe von binSuche höchstens entstehen.
Vollständige Lösung
links > rechts hinzu: höchstens 8 Aufrufe — und genauso groß ist die Rekursionstiefe.Mergesort sortiert die schon aufsteigend sortierte Reihung 1, 2, …, 32. Berechnen Sie die Anzahl der Vergleiche.
Vollständige Lösung
Quicksort mit dem letzten Element als Pivot erhält die sortierte Reihung 1, 2, …, 50. Bestätigen Sie durch Rechnung, dass Quicksort hier quadratisch arbeitet: Geben Sie die Anzahl der Vergleiche und die Rekursionstiefe an.
quicksort(a, 0, 49), (0, 48), …, (0, 0).Vollständige Lösung
Mergesort teilt ohne Vergleiche und mischt zwei Hälften mit höchstens \(n\) Vergleichen (vereinfacht). Stellen Sie die Rekursionsgleichung \(T(n)\) mit \(T(1) = 0\) auf und berechnen Sie \(T(64)\).
Vollständige Lösung
Für die Anzahl der Aufrufe von fib(n) (Abbruch bei n <= 1) gilt \(A(n) = 1 + A(n-1) + A(n-2)\) mit \(A(0) = A(1) = 1\). Weisen Sie durch Einsetzen nach, wie viele Aufrufe fib(10) braucht.