Startzeiten im Skilanglauf
13 BEAFB I–IIBei einem Langlaufrennen stehen die Startzeiten (in Sekunden nach dem ersten Start) aufsteigend sortiert in einer Reihung p. Die Rennleitung möchte wissen, wie viele Paare von Läuferinnen höchstens \(d\) Sekunden nacheinander starten. Dazu dient die abgebildete Methode. Der Operator && wertet seinen rechten Teil nur aus, wenn der linke wahr ist.
static int paareMitAbstand(int[] p, int d) { // p aufsteigend sortiert
int anzahl = 0;
for (int i = 0; i < p.length; i++) {
int j = i + 1;
while (j < p.length && p[j] - p[i] <= d) {
anzahl++;
j++;
}
}
return anzahl;
}- Ermitteln Sie für
p = {3, 5, 6, 10, 11, 17}undd = 2den Rückgabewert sowie die Anzahl der ausgewerteten Abstandsvergleichep[j] - p[i] <= d. (4 BE) - Beschreiben Sie, was die Methode berechnet, und erklären Sie, warum die innere Schleife beim ersten zu großen Abstand abbrechen darf. (3 BE)
- Bestimmen Sie die Anzahl der Abstandsvergleiche für eine Reihung der Länge \(n\) im besten Fall, wenn also alle benachbarten Startzeiten mehr als \(d\) auseinanderliegen. (2 BE)
- Leiten Sie die Anzahl der Abstandsvergleiche im ungünstigsten Fall her, wenn alle Startzeiten höchstens \(d\) auseinanderliegen, und ordnen Sie das Ergebnis einer Wachstumsklasse zu. (4 BE)
Hinweise
Hinweis zu Aufgabe a)
i, welche j geprüft werden und warum die innere Schleife endet.Hinweis zu Aufgabe b)
p[j], wenn schon p[j] - p[i] > d ist?Hinweis zu Aufgabe c)
i = 0 … n − 2 statt, wie viele für i = n − 1?Hinweis zu Aufgabe d)
j < p.length.Erwartungshorizont
Erwartungshorizont zu Aufgabe a)
| i | p[i] | geprüfte j | Abstände | Vergleiche | anzahl danach |
|---|---|---|---|---|---|
| 0 | 3 | 1, 2 | 2 ✓, 3 ✗ | 2 | 1 |
| 1 | 5 | 2, 3 | 1 ✓, 5 ✗ | 2 | 2 |
| 2 | 6 | 3 | 4 ✗ | 1 | 2 |
| 3 | 10 | 4, 5 | 1 ✓, 7 ✗ | 2 | 3 |
| 4 | 11 | 5 | 6 ✗ | 1 | 3 |
| 5 | 17 | — | j < 6 falsch | 0 | 3 |
Rückgabe 3, insgesamt 8 Abstandsvergleiche. Bei i = 5 ist j = 6 bereits zu groß; wegen && wird der Abstand nicht mehr berechnet.
Erwartungshorizont zu Aufgabe b)
Die Methode zählt alle Paare \((i, j)\) mit \(i < j\) und \(p[j] - p[i] \le d\). Weil p aufsteigend sortiert ist, gilt für alle späteren Indizes \(p[j+1] \ge p[j]\), die Abstände zu \(p[i]\) werden also nur größer. Ist ein Abstand zu groß, kann kein späteres Paar mit diesem \(i\) mehr zählen.
Erwartungshorizont zu Aufgabe c)
Für jedes \(i \le n - 2\) ist schon der erste Abstand zu groß: genau ein Vergleich. Für \(i = n - 1\) wird wegen j < p.length kein Abstand berechnet. Insgesamt \(n - 1\) Vergleiche — linear.
Erwartungshorizont zu Aufgabe d)
Jeder Abstand ist erlaubt; die innere Schleife prüft für festes \(i\) alle \(j = i + 1, \ldots, n - 1\): \(n - 1 - i\) Vergleiche. Summe:
\[\sum_{i=0}^{n-1} (n - 1 - i) = (n-1) + (n-2) + \ldots + 1 + 0 = \frac{n(n-1)}{2}\]Das liegt in \(O(n^2)\). Rückgabewert ist in diesem Fall ebenfalls \(\frac{n(n-1)}{2}\), weil jedes Paar zählt.
Entfernungstabelle
15 BEAFB II–IIIEin Routenplaner speichert die Fahrzeiten zwischen \(n\) Orten in einer Tabelle int[][] m mit \(n\) Zeilen und \(n\) Spalten; m[i][j] ist die Fahrzeit von Ort \(i\) nach Ort \(j\) in Minuten. Zwei Methoden werten die Tabelle aus.
static int maxZeilensumme(int[][] m) { // alle Einträge ≥ 0
int max = 0;
for (int i = 0; i < m.length; i++) {
int s = 0;
for (int j = 0; j < m[i].length; j++) {
s = s + m[i][j];
}
if (s > max) {
max = s;
}
}
return max;
}
static boolean istSymmetrisch(int[][] m) { // m hat n Zeilen und n Spalten
int n = m.length;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (m[i][j] != m[j][i]) {
return false;
}
}
}
return true;
}- Geben Sie für \(n = 5\) und allgemein an, wie oft in
maxZeilensummedie Anweisungs = s + m[i][j]und der Vergleichs > maxausgeführt werden. (3 BE) - Stellen Sie für
istSymmetrischdie Anzahl der Vergleichem[i][j] != m[j][i]im besten und im ungünstigsten Fall auf (\(n \ge 2\)) und leiten Sie den ungünstigsten Fall her. (4 BE) - Nehmen Sie Stellung zu der Aussage: „Beide Methoden enthalten zwei verschachtelte Schleifen, also sind sie gleich aufwendig.“ (4 BE)
- Verändern Sie
istSymmetrischzu einer Methodestatic int anzahlAbweichungen(int[][] m), die die Anzahl der Paare \(i < j\) mitm[i][j] != m[j][i]zurückgibt. Geben Sie an, wie viele Vergleiche die neue Methode braucht. (4 BE)
Hinweise
Hinweis zu Aufgabe a)
Hinweis zu Aufgabe b)
Hinweis zu Aufgabe c)
Hinweis zu Aufgabe d)
Erwartungshorizont
Erwartungshorizont zu Aufgabe a)
Die Addition steht in beiden Schleifen: \(n \cdot n\)-mal, für \(n = 5\) also 25-mal. Der Vergleich steht nur in der äußeren Schleife: \(n\)-mal, für \(n = 5\) also 5-mal. Die Anzahlen hängen nicht von den Einträgen ab.
Erwartungshorizont zu Aufgabe b)
Bester Fall: m[0][1] != m[1][0] — nach einem Vergleich wird false zurückgegeben. Ungünstigster Fall: Die Tabelle ist symmetrisch, alle Paare oberhalb der Diagonale werden geprüft. Für festes \(i\) läuft j von \(i + 1\) bis \(n - 1\):
Das liegt in \(O(n^2)\).
Erwartungshorizont zu Aufgabe c)
Die Aussage trifft nur für die Wachstumsklasse zu: Beide liegen im ungünstigsten Fall in \(O(n^2)\). Die Zahlen unterscheiden sich aber: maxZeilensumme braucht immer \(n^2\) Additionen (für \(n = 1000\): \(10^6\)), istSymmetrisch höchstens \(\frac{n(n-1)}{2}\) Vergleiche (499 500) — etwa die Hälfte, weil jedes Paar nur einmal betrachtet wird. Zudem kann istSymmetrisch vorzeitig enden und ist im besten Fall konstant. Fazit: gleiche Klasse, aber nicht gleicher Aufwand.
Erwartungshorizont zu Aufgabe d)
static int anzahlAbweichungen(int[][] m) {
int n = m.length;
int z = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (m[i][j] != m[j][i]) {
z++;
}
}
}
return z;
}Weil kein vorzeitiges Ende mehr möglich ist, braucht die Methode immer \(\frac{n(n-1)}{2}\) Vergleiche — bester und ungünstigster Fall fallen zusammen.