Messwerte über der Grenze
AFB I–IIEine Wetterstation speichert Tageshöchstwerte der Temperatur in °C in einer Reihung werte. Ein Programm zählt, an wie vielen Tagen eine Grenze überschritten wurde. Es verwendet die abgebildete Methode, die mit zaehleUeber(werte, grenze, 0) aufgerufen wird.
static int zaehleUeber(int[] werte, int grenze, int i) {
if (i == werte.length) {
return 0;
}
int rest = zaehleUeber(werte, grenze, i + 1);
if (werte[i] > grenze) {
return rest + 1;
}
return rest;
}- Beschreiben Sie, wie die Methode das Ergebnis ermittelt. Gehen Sie dabei auf Abbruchbedingung und Rekursionsschritt ein. 3 BE
- Wenden Sie die Methode auf
werte = {12, 31, 27, 8, 35}undgrenze = 25an. Stellen Sie die Aufrufe in einer Tabelle miti,werte[i],restund Rückgabewert dar. 5 BE - Implementieren Sie eine gleichwertige Methode
zaehleUeber(int[] werte, int grenze)ohne Selbstaufruf. 4 BE - Erläutern Sie, warum für eine Messreihe über 300 Jahre (etwa 110 000 Werte) die iterative Fassung vorzuziehen ist. 3 BE
Insgesamt 15 BE
Hinweise
Hinweis zu Aufgabe a)
Hinweis zu Aufgabe b)
Hinweis zu Aufgabe c)
Hinweis zu Aufgabe d)
Erwartungshorizont
Erwartungshorizont zu Aufgabe a)
Abbruchbedingung: Ist i gleich der Länge, ist kein Wert mehr übrig — Rückgabe 0. Rekursionsschritt: Die Methode zählt zuerst rekursiv die Überschreitungen ab i + 1 (rest) und addiert 1, falls werte[i] über der Grenze liegt. Ergebnis ist die Zahl der Werte ab Index i, die größer als grenze sind; beim Start mit 0 also in der ganzen Reihung.
Erwartungshorizont zu Aufgabe b)
| i | werte[i] | rest | werte[i] > 25 | Rückgabe |
|---|---|---|---|---|
| 5 | — | — | — | 0 (Abbruch) |
| 4 | 35 | 0 | wahr | 1 |
| 3 | 8 | 1 | falsch | 1 |
| 2 | 27 | 1 | wahr | 2 |
| 1 | 31 | 2 | wahr | 3 |
| 0 | 12 | 3 | falsch | 3 |
Die Tabelle ist in der Reihenfolge der Rückgaben notiert; aufgerufen wird in der Reihenfolge i = 0, 1, …, 5. Ergebnis 3.
Erwartungshorizont zu Aufgabe c)
static int zaehleUeber(int[] werte, int grenze) {
int anzahl = 0;
for (int i = 0; i < werte.length; i++) {
if (werte[i] > grenze) {
anzahl++;
}
}
return anzahl;
}Erwartungshorizont zu Aufgabe d)
Die rekursive Fassung legt für jeden Index einen Rahmen an, bei 110 000 Werten also rund 110 000 gleichzeitig offene Aufrufe. Der Aufrufstapel von Java reicht typischerweise nur für einige tausend bis zehntausend Ebenen, es droht ein StackOverflowError. Die Schleife braucht unabhängig von der Länge nur einen Rahmen und ist außerdem etwas schneller, da kein Aufruf verwaltet werden muss. Beide haben dieselbe Zahl von Vergleichen.
Wege durch den Stadtplan
AFB II–IIIIn einer Stadt mit schachbrettartigen Straßen will ein Kurierdienst von der Kreuzung (0 | 0) zur Kreuzung (x | y) fahren und dabei nur nach Osten oder Norden abbiegen. Die Methode wege berechnet die Anzahl der möglichen Routen.
static long wege(int x, int y) {
if (x == 0 || y == 0) {
return 1;
}
return wege(x - 1, y) + wege(x, y - 1);
}- Bestimmen Sie
wege(2, 2)und die Anzahl der dabei entstehenden Aufrufe vonwege. 4 BE - Analysieren Sie, welche Aufrufe bei
wege(2, 2)mehrfach vorkommen, und schätzen Sie ab, welche Folgen das fürwege(16, 16)mit dem Ergebnis 601 080 390 hat. 4 BE - Entwickeln Sie eine Methode
wegeTabelle(int x, int y), die ohne Selbstaufruf auskommt und die Zwischenergebnisse in einer zweidimensionalen Reihung speichert. 6 BE - Beurteilen Sie beide Methoden hinsichtlich Laufzeit und Speicherbedarf. 4 BE
Insgesamt 18 BE
Hinweise
Hinweis zu Aufgabe a)
Hinweis zu Aufgabe b)
Hinweis zu Aufgabe c)
t[i][j] hängt nur von Werten links und darunter ab (Kapitel 2, zweidimensionale Reihungen).Hinweis zu Aufgabe d)
Erwartungshorizont
Erwartungshorizont zu Aufgabe a)
\(\text{wege}(2,2) = \text{wege}(1,2) + \text{wege}(2,1)\) mit \(\text{wege}(1,2) = \text{wege}(0,2) + \text{wege}(1,1) = 1 + 2 = 3\) und ebenso \(\text{wege}(2,1) = 3\): Ergebnis 6.
Aufrufe: \(C(1,1) = 3\), \(C(1,2) = C(2,1) = 1 + C(1,1) + 1 = 5\), \(C(2,2) = 1 + 5 + 5 = 11\).
Erwartungshorizont zu Aufgabe b)
wege(1, 1) wird zweimal berechnet (von wege(1, 2) und von wege(2, 1) aus), die Randaufrufe wie wege(0, 1) ebenfalls mehrfach. Da nur die Blätter den Wert 1 liefern und alles andere Summen sind, braucht das Ergebnis 601 080 390 genauso viele Blätter; der Aufrufbaum ist ein vollständiger Binärbaum mit rund \(2 \cdot 601\,080\,390 - 1 \approx 1{,}2\) Milliarden Aufrufen. Das dauert selbst auf schnellen Rechnern Sekunden, und schon wenige Kreuzungen mehr vervielfachen die Zeit.
Erwartungshorizont zu Aufgabe c)
static long wegeTabelle(int x, int y) {
long[][] t = new long[x + 1][y + 1];
for (int i = 0; i <= x; i++) {
for (int j = 0; j <= y; j++) {
if (i == 0 || j == 0) {
t[i][j] = 1;
} else {
t[i][j] = t[i - 1][j] + t[i][j - 1];
}
}
}
return t[x][y];
}wegeTabelle(2, 2) liefert 6, wegeTabelle(16, 16) liefert 601 080 390 nach nur 289 Tabellenfeldern.
Erwartungshorizont zu Aufgabe d)
Laufzeit: wege braucht etwa doppelt so viele Aufrufe, wie es Routen gibt — das wächst exponentiell mit x + y. wegeTabelle berechnet jedes Feld genau einmal: \((x+1)(y+1)\) Schritte. Speicher: wege hat höchstens \(x + y + 1\) Rahmen gleichzeitig auf dem Stapel, wegeTabelle braucht eine Tabelle mit \((x+1)(y+1)\) Feldern. Der zusätzliche Speicher ist klein, der Zeitgewinn gewaltig; für praktische Größen ist die Tabelle klar vorzuziehen. Die rekursive Methode bleibt als lesbare Beschreibung des Zusammenhangs wertvoll.