MINT üben

Operationen zählen

Zwei Aufgaben im Abiturformat — von Startzeiten im Skilanglauf bis zur Entfernungstabelle eines Routenplaners.

Dein Fortschritt:
0 / 0 Aufgaben
1

Startzeiten im Skilanglauf

13 BEAFB I–II

Bei 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.

Methode paareMitAbstand
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;
}
  1. Ermitteln Sie für p = {3, 5, 6, 10, 11, 17} und d = 2 den Rückgabewert sowie die Anzahl der ausgewerteten Abstandsvergleiche p[j] - p[i] <= d. (4 BE)
  2. Beschreiben Sie, was die Methode berechnet, und erklären Sie, warum die innere Schleife beim ersten zu großen Abstand abbrechen darf. (3 BE)
  3. 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)
  4. 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)
Notieren Sie für jedes i, welche j geprüft werden und warum die innere Schleife endet.
Hinweis zu Aufgabe b)
Was gilt für alle späteren p[j], wenn schon p[j] - p[i] > d ist?
Hinweis zu Aufgabe c)
Wie viele Vergleiche finden für i = 0 … n − 2 statt, wie viele für i = n − 1?
Hinweis zu Aufgabe d)
Dann endet die innere Schleife immer über j < p.length.