MINT üben

Algorithmen mit DynArray

Dreißig Übungen zu Summe, Maximum, Suche und dem Löschen in der Schleife — von AFB I bis AFB III.

Dein Fortschritt:
0 / 0 Aufgaben
1

Übungsaufgaben

Dreißig Übungen in gemischter Reihenfolge — du klickst, ziehst, ordnest, rechnest und knobelst. Jede Übung gibt dir sofort eine Rückmeldung, und zu jeder Aufgabe gibt es zwei gestufte Tipps: Der erste zeigt die Richtung, der zweite den entscheidenden Schritt. Die Chips zeigen das Anforderungsniveau: AFB I heißt wiedergeben und direkt anwenden, AFB II selbst entscheiden und verknüpfen, AFB III begründen, beurteilen oder eine Falle durchschauen. Aufgaben mit dem Chip Mix verbinden Wissen aus früheren Unterkapiteln, bei Trick steckt eine Falle drin. Fährst du über ein unterstrichenes Arbeitswort, siehst du, was es genau von dir verlangt.

A1
Hitzetage zählen
AFB I

Eine Wetterstation speichert die Tageshöchsttemperaturen als DynArray<Integer> temp. Stelle den Algorithmus dar, der die Tage mit mehr als 30 Grad zählt: Bringe die Arbeitsschritte in die richtige Reihenfolge.

Ziehe die Karten in die richtige Reihenfolge — mit der Tastatur: ↑/↓ verschiebt, Shift+↑/↓ wechselt nur den Fokus.
1 Einen Zähler anlegen und auf 0 setzen
2 Eine Schleife über alle Indizes von temp beginnen
3 Die Temperatur an Index i lesen
4 Ist sie größer als 30, den Zähler um 1 erhöhen
5 Nach der Schleife den Zähler zurückgeben
Der Zähler muss vor der Schleife angelegt werden, sonst würde er bei jedem Durchlauf neu auf 0 gesetzt. Zurückgegeben wird erst nach dem letzten Durchlauf.
Überlege, was vor der Schleife, was in der Schleife und was erst nach der Schleife passieren muss.
Lesen und Prüfen gehören in den Schleifenrumpf: erst die Temperatur an Index i lesen, dann entscheiden, ob gezählt wird.
A2
Namen im Chor suchen
AFB II

Die Anmeldungen zum Schulchor stehen in DynArray<String> namen:

0Eva1Tom2Ida3Max4Lea

Die Methode indexVon durchläuft die Reihung von vorn und vergleicht jedes Element mit equals. Ordne jede Suche nach der Zahl der Vergleiche ein. Jede Zeile beginnt wieder mit der Reihung oben.

Wähle für jede Zeile die Zahl der equals-Vergleiche, bis die Suche endet. Mit der Tastatur: Tab zur Zeile, ←/→ zwischen den Stufen, Enter setzt.
1 Vergleich5 Vergleiche
Suche nach "Ida"
Suche nach "Zoe" (steht nicht in der Reihung)
Suche nach "Max", nachdem delete(1) ausgeführt wurde
Suche nach "Lea", nachdem delete(0) ausgeführt wurde
Suche nach "Eva", nachdem insertAt(0, "Kai") ausgeführt wurde
Ein Treffer an Index i kostet i + 1 Vergleiche. Fehlt der Name, werden alle Elemente verglichen. Nach delete oder insertAt zählt der neue Index: Max steht nach delete(1) an Index 2, Lea nach delete(0) an Index 3 und Eva nach insertAt(0, "Kai") an Index 1.
Ein Name an Index i wird mit dem (i + 1)-ten Vergleich gefunden, denn gezählt wird ab 0, vergleichen musst du aber auch den Index 0.
Schreibe bei den letzten drei Zeilen zuerst die veränderte Reihung auf, dann suche darin den Index.
A3
Maximum Schritt für Schritt
AFB II

Analysiere den folgenden Algorithmus, der auf l = [3, 8, 5, 9, 1] läuft:

int max = l.getItem(0);
for (int i = 1; i < l.getLength(); i++) {
    if (l.getItem(i) > max) {
        max = l.getItem(i);
    }
}
return max;

Arbeite die Kette Schritt für Schritt ab: Erst wenn ein Schritt stimmt, wird der nächste freigeschaltet. Enter prüft.
  1. max nach der ersten Zeile
  2. max nach dem Durchlauf mit i = 2
  3. max nach dem Durchlauf mit i = 3
  4. Wie oft wird max insgesamt ersetzt?
Bei i = 2 ist 5 kleiner als 8 — max bleibt. Ersetzt wird nur bei 8 und bei 9.
Verfolge den Algorithmus mit dem Finger durch die Reihung: Was steht nach der ersten Zeile in max?
max ändert sich nur, wenn das aktuelle Element größer ist als der bisherige Wert — zähle diese Fälle.