MINT lernen

Algorithmen mit DynArray

Zwei Abituraufgaben zu Durchlauf und Löschen — mit Hinweisen und Erwartungshorizont.

Dein Fortschritt:
0 / 0 Aufgaben
1

Messreihe einer Wetterstation

AFB I–II

Eine Wetterstation speichert die Mittagstemperaturen einer Woche in DynArray<Double> t = [12,5; 14,0; 9,5; 16,0; 11,0]. Gegeben ist die Methode:

public int gesucht(DynArray<Double> t) {
    int pos = 0;
    for (int i = 1; i < t.getLength(); i++) {
        if (t.getItem(i) > t.getItem(pos)) {
            pos = i;
        }
    }
    return pos;
}
  1. Stellen Sie den Ablauf der Methode für die gegebene Messreihe in einer Tracetabelle dar (Spalten i, t.getItem(i), t.getItem(pos), pos).
  2. Erläutern Sie, was die Methode berechnet, und warum es sinnvoll ist, einen Index statt eines Temperaturwertes zurückzugeben.

Hinweise

Hinweis zu Aufgabe a)
Die Schleife beginnt bei i = 1. pos ändert sich nur, wenn der Vergleich wahr ist.
Hinweis zu Aufgabe b)
Überlegen Sie, welche Information man mit dem Index zusätzlich erhält.

Erwartungshorizont

Erwartungshorizont zu Aufgabe a)
it.getItem(i)t.getItem(pos)pos
——12,50
114,012,51
29,514,01
316,014,03
411,016,03

Rückgabe: 3.

Erwartungshorizont zu Aufgabe b)

Die Methode bestimmt die Position der höchsten Temperatur (erstes Maximum). Mit dem Index erhält man neben dem Wert (t.getItem(pos)) auch den Tag der Woche — und könnte z. B. in einer zweiten Reihung mit Datumsangaben unter demselben Index nachsehen. Aus dem Wert allein lässt sich der Tag nicht zurückgewinnen.

2

Messfehler entfernen

AFB II–III

Bei Sensorfehlern speichert die Station den Wert −999. Ein Schüler hat folgende Methode geschrieben:

public void entferneFehler(DynArray<Double> t) {
    for (int i = 0; i < t.getLength(); i++) {
        if (t.getItem(i) == -999) {
            t.delete(i);
        }
    }
}
  1. Analysieren Sie die Methode für t = [5,0; −999; −999; 7,5].
  2. Implementieren Sie eine korrigierte Fassung der Methode.
  3. Schätzen Sie ab, wie viele Elemente insgesamt verschoben werden müssen, wenn eine Reihung mit 1000 Werten nur aus Fehlwerten besteht — einmal für die Rückwärts-Variante, einmal für eine Variante, die immer delete(0) ausführt.

Hinweise

Hinweis zu Aufgabe a)
Führen Sie eine Tracetabelle mit i und der aktuellen Reihung. Was steht nach dem ersten Löschen an Index 1?
Hinweis zu Aufgabe b)
Zwei Wege: rückwärts laufen, oder i nur erhöhen, wenn nicht gelöscht wurde.
Hinweis zu Aufgabe c)
Bei delete(i) rücken alle Elemente hinter Index i nach. Wie viele stehen bei der Rückwärts-Variante jeweils dahinter?

Erwartungshorizont

Erwartungshorizont zu Aufgabe a)

i = 0: 5,0 bleibt. i = 1: −999 wird gelöscht → [5,0; −999; 7,5]; das zweite −999 rückt auf Index 1. i = 2: 7,5 bleibt. Ende. Ergebnis [5,0; −999; 7,5] — ein Fehlwert bleibt stehen, weil nach dem Löschen das nachgerückte Element übersprungen wird. Der Fehler tritt immer dann auf, wenn zwei Fehlwerte direkt aufeinander folgen.

Erwartungshorizont zu Aufgabe b)
public void entferneFehler(DynArray<Double> t) {
    for (int i = t.getLength() - 1; i >= 0; i--) {
        if (t.getItem(i) == -999) {
            t.delete(i);
        }
    }
}

Gleichwertig: while-Schleife, die i nur im else-Zweig erhöht.

Erwartungshorizont zu Aufgabe c)

Rückwärts: Gelöscht wird stets das letzte Element, dahinter steht nichts — 0 Verschiebungen. Mit delete(0): 999 + 998 + … + 1 = 999 · 1000 : 2 ≈ 500 000 Verschiebungen. Die Rückwärts-Variante ist also nicht nur korrekt, sondern hier auch deutlich effizienter.