Aufgabenblock — AFB III
Begründen statt nur ausführen: Behauptungen widerlegen, Algorithmen entwerfen und implementieren, Verfahren beurteilen, Fehler finden und Formeln allgemein zeigen. Jede Aufgabe hat ein prüfbares Kernergebnis — formuliere die Begründung trotzdem in ganzen Sätzen, bevor du die Musterlösung aufklappst.
Mia behauptet: „Auf einer sortierten Reihung ist die binäre Suche immer schneller als die lineare Suche.“ Widerlegen Sie die Behauptung mit der sortierten Reihung gerade = {2, 4, 6, …, 62} (31 Elemente).
Geben Sie für Ihr Gegenbeispiel die Suche nach dem Wert 2 an: Wie viele Elemente sieht die binäre Suche an?
Musterlösung anzeigen
Musterlösung: Gesucht wird der Wert 2, das erste Element. Die lineare Suche findet ihn nach genau einem Vergleich. Die binäre Suche beginnt in der Mitte: mitte = 15, 7, 3, 1, 0 — erst im fünften Schritt ist gerade[0] = 2 erreicht.
In diesem Fall ist die lineare Suche also schneller; die Behauptung ist widerlegt. Richtig ist: Im ungünstigsten Fall (und im Mittel bei großen \(n\)) braucht die binäre Suche viel weniger Schritte (\(\lfloor\log_2 n\rfloor+1\) statt \(n\)).
Aus den Punktzahlen eines Wettbewerbs soll der zweitgrößte verschiedene Wert ermittelt werden, ohne die Reihung zu sortieren und mit nur einem Durchlauf.
Entwerfen Sie einen Algorithmus als Struktogramm. Welchen Wert liefert er für die abgebildete Reihung?
x > max: zweit ← max, max ← x. Sonst, wenn x < max und x > zweit: zweit ← x. Gleiche Werte wie max ignorieren.Musterlösung anzeigen
Musterlösung:
Ablauf: max/zweit = 14/−∞ → 27/14 → 27/14 (9) → 27/14 (27 gleich max, ignoriert) → 27/21 → 27/21 (18). Ergebnis 21. Ohne die Bedingung punkte[i] < max würde die zweite 27 als „zweitgrößter“ Wert gespeichert. Der Algorithmus braucht höchstens \(2(n-1)\) Vergleiche — linear, statt quadratisch wie Sortieren mit Selectionsort.
Bevor ein Programm binär sucht, soll es prüfen, ob die Reihung aufsteigend sortiert ist (gleiche Nachbarn sind erlaubt). Implementieren Sie die Methode boolean istSortiert(int[] a) in Java so, dass sie beim ersten falsch geordneten Nachbarpaar abbricht.
Wie viele Vergleiche zwischen Nachbarn führt Ihre Methode für die abgebildete Reihung aus?
a[i − 1] und a[i] für i ab 1 prüfen; beim ersten Paar mit a[i] < a[i − 1] sofort false zurückgeben.Warum so? Sortiert heißt: kein Paar steht falsch herum. Ein einziges falsches Paar reicht als Gegenbeweis.false.Musterlösung anzeigen
Musterlösung:
public static boolean istSortiert(int[] a) {
for (int i = 1; i < a.length; i++) {
if (a[i] < a[i - 1]) {
return false; // erstes falsches Paar
}
}
return true; // kein falsches Paar gefunden
}
Für die Reihung werden (2,5), (5,5), (5,9) und (9,4) geprüft: 4 Vergleiche, Ergebnis false. Bei einer sortierten Reihung der Länge \(n\) sind es \(n-1\) Vergleiche. Wichtig: return true steht nach der Schleife; ein else return true in der Schleife würde schon nach dem ersten Paar antworten. Die Bedingung < (nicht <=) lässt gleiche Nachbarn zu.