Aufgabenblock — AFB II
Zehn Aufgaben aus allen Unterkapiteln: Programme analysieren, zweidimensionale Reihungen auswerten, Such- und Sortierverfahren verfolgen und Vergleichszahlen herleiten — mit gestuften Tipps, wenn du nicht weiterkommst.
Beim Sportfest werden die Weiten einer Riege (in cm) ausgewertet:
int[] weite = {412, 385, 450, 398, 471, 405};
int summe = 0;
for (int w : weite) {
summe = summe + w;
}
int schnitt = summe / weite.length;
int besser = 0;
for (int w : weite) {
if (w > schnitt) {
besser++;
}
}Analysieren Sie das Programm: Welche Werte haben schnitt und besser am Ende? Beachten Sie den Datentyp von schnitt.
int fällt der Rest weg. Dann zählen, welche Weiten echt größer als 420 sind.Vollständige Lösung
2521 / 6 ist eine Division zweier int-Werte, also ganzzahlig: schnitt = 420 (der genaue Mittelwert wäre 420,17). Größer als 420 sind nur 450 und 471: besser = 2. Hinweis: Für den genauen Mittelwert müsste man z. B. (double) summe / weite.length rechnen.Ein Höhenprofil einer Wanderung (in 100 m) wird mit folgendem Programmausschnitt untersucht:
int z = 0;
for (int i = 1; i < h.length; i++) {
if (h[i] < h[i - 1]) {
z++;
}
}Untersuchen Sie, wie oft der Schleifenrumpf ausgeführt wird und welchen Wert z am Ende hat. Beschreiben Sie für sich in einem Satz, was z zählt.
i = 1, weil immer mit dem Vorgänger h[i − 1] verglichen wird.Vollständige Lösung
i von 1 bis 6, also 6 Durchläufe. Ein echter Abstieg liegt bei 9 → 7, 7 → 3 und 8 → 6 vor; 7 → 7 zählt nicht. z = 3 ist die Anzahl der Abschnitte, in denen es bergab geht. Würde die Schleife bei i = 0 starten, gäbe es beim Zugriff h[−1] einen Laufzeitfehler.Ein kleiner Kinosaal hat 4 Reihen mit je 6 Plätzen. saal[r][p] ist 1, wenn der Platz besetzt ist, sonst 0.
| saal | p = 0 | p = 1 | p = 2 | p = 3 | p = 4 | p = 5 |
|---|---|---|---|---|---|---|
| r = 0 | 1 | 1 | 0 | 1 | 1 | 0 |
| r = 1 | 0 | 0 | 1 | 1 | 1 | 1 |
| r = 2 | 1 | 0 | 0 | 0 | 1 | 0 |
| r = 3 | 1 | 1 | 1 | 1 | 0 | 1 |
Ein Programm soll mit zwei verschachtelten Schleifen die Anzahl aller besetzten Plätze bestimmen und den Index der Reihe mit den meisten freien Plätzen ausgeben. Werten Sie die Tabelle so aus, wie es das Programm tun würde.
r, innere über die Plätze p; für jede Reihe die Nullen zählen.Vollständige Lösung
for (int r = 0; r < saal.length; r++) { int frei = 0; for (int p = 0; p < saal[r].length; p++) { if (saal[r][p] == 0) frei++; } if (frei > maxFrei) { maxFrei = frei; besteReihe = r; } }Gegeben ist die quadratische Reihung m und ein Programmausschnitt:
int[][] m = {{4, 1, 7},
{2, 8, 3},
{6, 5, 9}};
int s = 0;
for (int i = 0; i < m.length; i++) {
for (int j = 0; j < i; j++) {
s = s + m[i][j];
}
}Ermitteln Sie den Endwert von s und die Anzahl der Additionen, die ausgeführt werden.
j < i. Schreiben Sie für jedes i auf, welche j vorkommen.Vollständige Lösung
m[1][0] = 2, m[2][0] = 6, m[2][1] = 5. \(s = 2 + 6 + 5 = 13\) mit \(0 + 1 + 2 = 3\) Additionen. Allgemein sind es bei einer \(n\times n\)-Reihung \(\frac{n(n-1)}{2}\) Additionen — dieselbe Zahl wie die Vergleiche bei Selectionsort.Die sortierte Reihung enthält Losnummern einer Tombola, die schon gezogen wurden:
Stellen Sie die binäre Suche nach 50 in einer Tracetabelle mit links, rechts, mitte, los[mitte] dar. Wie viele Elemente werden angesehen, und welchen Wert hat links, wenn die Schleife endet?
links = 0, rechts = 14. Die Schleife läuft, solange links ≤ rechts.Vollständige Lösung
| links | rechts | mitte | los[mitte] | Vergleich |
|---|---|---|---|---|
| 0 | 14 | 7 | 34 | 34 < 50 |
| 8 | 14 | 11 | 52 | 52 > 50 |
| 8 | 10 | 9 | 43 | 43 < 50 |
| 10 | 10 | 10 | 47 | 47 < 50 |
| 11 | 10 | — | — | links > rechts: Ende |
links = 11 > rechts = 10: 50 ist nicht enthalten, Rückgabe −1. links = 11 ist genau die Stelle, an der 50 eingefügt werden müsste, damit die Reihung sortiert bleibt.Ein Online-Shop hat 5000 Artikelnummern sortiert in einer Reihung gespeichert.
a) Vergleichen Sie die Anzahl der angesehenen Elemente im ungünstigsten Fall: lineare gegen binäre Suche. b) Wie viele Artikel darf die Reihung höchstens enthalten, damit die binäre Suche im ungünstigsten Fall mit 20 Schritten auskommt?
Vollständige Lösung
Die Punktzahlen eines Quiz werden mit Insertionsort aufsteigend sortiert. Der Schlüssel a[i] wird mit den Elementen links davon verglichen; größere rücken eine Stelle nach rechts.
Bestimmen Sie den Wert an Index 3, nachdem das Element mit Index 3 eingefügt wurde (Durchlauf i = 3), und die Anzahl aller Vergleiche zwischen Elementen bis zum Ende.
i sortiert. Ein Vergleich zählt auch dann, wenn er das Einfügen beendet.Vollständige Lösung
| i | Schlüssel | Reihung danach | Vergleiche |
|---|---|---|---|
| 1 | 18 | 18 31 25 12 40 21 | 1 |
| 2 | 25 | 18 25 31 12 40 21 | 2 |
| 3 | 12 | 12 18 25 31 40 21 | 3 |
| 4 | 40 | 12 18 25 31 40 21 | 1 |
| 5 | 21 | 12 18 21 25 31 40 | 4 |
i = 3 steht 31 an Index 3. Insgesamt 11 Vergleiche (bei i = 3 endet die Schleife am Rand, bei i = 5 am Vergleich 18 < 21) und 8 Verschiebungen.Zwölf Läuferinnen werden nach ihrer Zeit sortiert. Leiten Sie die Anzahl der Vergleiche von Insertionsort her a) wenn die Zeiten schon aufsteigend sortiert sind und b) wenn sie absteigend sortiert sind. c) Wie viele Vergleiche braucht Selectionsort in beiden Fällen?
Vollständige Lösung
Ein Bubblesort merkt sich in einer Variablen getauscht, ob in einem Durchlauf vertauscht wurde, und bricht ab, wenn das nicht der Fall war. Jeder Durchlauf ist eine Stelle kürzer als der vorige.
Überprüfen Sie, nach wie vielen Durchläufen das Verfahren abbricht und wie viele Vergleiche es bis dahin braucht.
Vollständige Lösung
getauscht bleibt false → Abbruch. Zusammen 9 Vergleiche statt \(\frac{6\cdot5}{2} = 15\) ohne Abbruchbedingung. Der zweite Durchlauf ist nötig: Erst er bestätigt, dass nichts mehr zu tun ist.Ein Programm sortiert 10 000 Messwerte mit Selectionsort in 0,2 s und sucht danach einen Wert binär mit 14 angesehenen Elementen (ungünstigster Fall). Schätzen Sie ab, wie lange das Sortieren von 40 000 Messwerten dauert und wie viele Elemente die binäre Suche dann höchstens ansieht.