MINT üben

Strategie Teile und herrsche

Den heißesten Tag der Woche finden und riesige Potenzen berechnen — zweimal hilft das Halbieren.

Dein Fortschritt:
0 / 0 Aufgaben
1

Die Wetterstation

14 BEAFB I–II

Eine Schul-Wetterstation speichert die Tageshöchsttemperaturen einer Woche in °C in der Reihung t. Um den heißesten Tag zu finden, wurde die abgebildete Methode groesster nach dem Prinzip Teile und herrsche programmiert. Der Aufruf lautet groesster(t, 0, t.length - 1).

Reihung t und Methode groesster
static int groesster(int[] a, int links, int rechts) {
    if (links == rechts) {
        return a[links];
    }
    int mitte = (links + rechts) / 2;
    int g1 = groesster(a, links, mitte);
    int g2 = groesster(a, mitte + 1, rechts);
    if (g1 >= g2) {
        return g1;
    }
    return g2;
}
  1. Beschreiben Sie am Beispiel der Methode groesster die drei Schritte der Strategie Teile und herrsche und nennen Sie den Basisfall. (3 BE)
  2. Stellen Sie die Aufrufe von groesster(t, 0, 5) als Aufrufbaum dar. Notieren Sie an jedem Aufruf die Parameter links, rechts und den Rückgabewert. (5 BE)
  3. Geben Sie die Anzahl der Aufrufe und die Anzahl der Vergleiche g1 >= g2 für diese Reihung an. Verallgemeinern Sie beide Anzahlen für eine Reihung mit \(n\) Elementen. (3 BE)
  4. Implementieren Sie nach demselben Prinzip eine Methode static int anzahlUeber(int[] a, int links, int rechts, int grenze), die zählt, an wie vielen Tagen die Temperatur über grenze lag. (3 BE)

Hinweise

Hinweis zu Aufgabe a)
Suchen Sie im Quelltext die Stelle, an der geteilt wird, die rekursiven Aufrufe und die Stelle, an der zwei Ergebnisse verbunden werden.
Hinweis zu Aufgabe b)
Der erste Aufruf teilt bei mitte = 2. Zeichnen Sie für jeden Aufruf zwei Kinder, bis die Bereiche nur noch ein Element haben.
Hinweis zu Aufgabe c)
Zählen Sie die Knoten Ihres Baums. Jeder Knoten mit zwei Kindern vergleicht genau einmal.
Hinweis zu Aufgabe d)
Der Basisfall liefert 1 oder 0; das Zusammenführen ist eine Addition.