Wasserverbrauch einer Woche
AFB I–IIEin digitaler Wasserzähler speichert den Tagesverbrauch einer Familie (in Litern) in einer Reihung v. Die Abbildung zeigt die Werte einer Woche und einen Algorithmus zur Auswertung.
- Stellen Sie den Ablauf des Algorithmus
auswertenfür die abgebildete Reihung in einer Tracetabelle mit den Spalteni,v[i],summe, Bedingung undmaxTagdar. - Beschreiben Sie, welche Bedeutung die beiden Rückgabewerte im Sachzusammenhang haben, und geben Sie die Ergebnisse für die abgebildete Woche an.
- Der durchschnittliche Tagesverbrauch soll als ganze Zahl mit
summe / 7berechnet werden, wobei/bei ganzen Zahlen ganzzahlig dividiert. Wenden Sie diese Berechnung auf die Woche an und bewerten Sie die Abweichung vom exakten Wert. - Implementieren Sie in Java eine Methode
int tageUeber(int[] v, int grenze), die zurückgibt, an wie vielen Tagen der Verbrauch übergrenzelag.
Hinweise
Hinweis zu Aufgabe a)
Hinweis zu Aufgabe b)
Hinweis zu Aufgabe c)
Hinweis zu Aufgabe d)
Erwartungshorizont
Erwartungshorizont zu Aufgabe a)
| i | v[i] | summe | v[i] > v[maxTag] | maxTag |
|---|---|---|---|---|
| – | – | 0 | – | 0 |
| 0 | 182 | 182 | falsch | 0 |
| 1 | 205 | 387 | wahr | 1 |
| 2 | 176 | 563 | falsch | 1 |
| 3 | 240 | 803 | wahr | 3 |
| 4 | 198 | 1001 | falsch | 3 |
| 5 | 310 | 1311 | wahr | 5 |
| 6 | 265 | 1576 | falsch | 5 |
Bei i = 0 wird v[0] mit sich selbst verglichen: 182 > 182 ist falsch.
Erwartungshorizont zu Aufgabe b)
summe ist der Gesamtverbrauch der Woche: 1576 Liter. maxTag ist der Index des Tages mit dem höchsten Verbrauch: 5, also Samstag mit 310 Litern. Bei gleich hohen Werten liefert der Algorithmus wegen > den ersten dieser Tage.
Erwartungshorizont zu Aufgabe c)
\(1576 / 7 = 225\) (ganzzahlig, Rest 1). Exakt sind es \(1576/7\approx225{,}14\) Liter. Die Abweichung von etwa 0,14 Liter ist hier unerheblich; sie beträgt aber bis zu knapp 1 Liter und wird bei kleinen Werten relativ groß. Für einen genauen Wert muss mit Kommazahlen gerechnet werden (in Java z. B. (double) summe / 7).
Erwartungshorizont zu Aufgabe d)
int tageUeber(int[] v, int grenze) {
int anzahl = 0;
for (int i = 0; i < v.length; i++) {
if (v[i] > grenze) {
anzahl++;
}
}
return anzahl;
}Eine for-each-Schleife for (int x : v) ist ebenso richtig, weil nur gelesen wird. Für die abgebildete Woche liefert tageUeber(v, 200) den Wert 4.
Laufzeiten beim Sportfest
AFB II–IIIBeim 100-m-Lauf eines Sportfests werden die Zeiten (in Sekunden) in einer Reihung zeit gespeichert, z. B. zeit = {13.4, 12.9, 14.1, 12.6, 13.0, 15.2}. Eine Schülerin hat folgenden Algorithmus für die Siegerzeit geschrieben:
bester ← 0
für i von 0 bis Länge von zeit − 1
wenn zeit[i] < bester dann
bester ← zeit[i]
gib bester zurück
- Analysieren Sie den Algorithmus: Geben Sie an, welchen Wert er für das Beispiel zurückgibt, und begründen Sie, warum er für keine Eingabe eine richtige Siegerzeit liefert.
- Verändern Sie den Algorithmus so, dass er korrekt arbeitet und statt der Siegerzeit die Startnummer (Index) des schnellsten Läufers zurückgibt. Stellen Sie das Ergebnis als Struktogramm dar.
- Für die Siegerehrung sollen alle Läuferinnen und Läufer gezählt werden, deren Zeit höchstens 5 % über der Siegerzeit liegt. Entwerfen Sie dafür einen Algorithmus als Struktogramm und geben Sie das Ergebnis für das Beispiel an.
- Schätzen Sie die Anzahl der Vergleiche zwischen zwei Zeiten ab, die Ihr Algorithmus aus Teil c) bei \(n\) Läufern benötigt. Vergleichen Sie mit einem Verfahren, das für jeden Läufer einzeln alle anderen Zeiten durchgeht, um zu prüfen, ob er der Sieger ist.
Hinweise
Hinweis zu Aufgabe a)
Hinweis zu Aufgabe b)
pos und vergleicht mit zeit[pos].Hinweis zu Aufgabe c)
Hinweis zu Aufgabe d)
Erwartungshorizont
Erwartungshorizont zu Aufgabe a)
Der Algorithmus gibt 0 zurück. Da alle Zeiten positiv sind, ist die Bedingung zeit[i] < 0 nie erfüllt; bester behält den Startwert 0, der gar keine gemessene Zeit ist. Das gilt für jede Eingabe mit positiven Zeiten, also für alle realen Läufe. Ursache ist der Startwert: Er muss ein Element der Reihung sein, z. B. zeit[0].
Erwartungshorizont zu Aufgabe b)
Für das Beispiel: pos = 3 (12,6 s). Beginnt die Schleife bei 0, ist das ebenfalls richtig, kostet aber einen unnötigen Vergleich.
Erwartungshorizont zu Aufgabe c)
Beispiel: Grenze \(1{,}05\cdot12{,}6=13{,}23\) s. Darunter bzw. gleich: 12,9; 12,6; 13,0 → 3 Personen (die Siegerin bzw. der Sieger zählt mit). Der Aufruf von schnellster aus b) darf auch ausgeschrieben werden.
Erwartungshorizont zu Aufgabe d)
Erster Durchlauf (Minimum): \(n-1\) Vergleiche. Zweiter Durchlauf (Zählen): \(n\) Vergleiche. Zusammen \(2n-1\), also linear in \(n\); bei 1000 Läufern 1999 Vergleiche. Das Vergleichsverfahren braucht für jeden der \(n\) Läufer bis zu \(n-1\) Vergleiche, also bis zu \(n(n-1)\) — bei 1000 Läufern 999 000. Bei doppelter Teilnehmerzahl verdoppelt sich der Aufwand des eigenen Algorithmus nur, der des Vergleichsverfahrens vervierfacht sich ungefähr.