Algorithmen üben

Spiel den Code durch: Arrays, binäre Suche, Rekursion und Fehlersuche. Für Fachinformatiker Anwendungsentwicklung in Teil 2.

Dieses Thema gehört zu Teil 2 der Abschlussprüfung (AP2), vor allem für Anwendungsentwicklung. Einfache Schleifen für die AP1 übst du im Thema Pseudocode.

Algorithmen in Pseudocode

In der AP2 musst du Code lesen, Werte verfolgen und Fehler finden. Am sichersten ist ein Schreibtischtest: eine Tabelle mit einer Spalte je Variable, eine Zeile je Schritt.

Arrays

  • Arrays beginnen meist bei Index 0. Das letzte Element ist a[laenge(a) − 1].
  • Bei verschachtelten Schleifen läuft die innere bei jedem Durchlauf der äußeren komplett durch.
  • Zweidimensional: m[i][j] ist Zeile i, Spalte j. Hauptdiagonale: i = j.

Binäre Suche

Nur in sortierten Arrays. In jedem Schritt wird die Mitte geprüft und die Hälfte verworfen, in der der Wert nicht liegen kann.

Beispiel: a = [3, 8, 15, 22, 41, 50, 63, 77, 90], gesucht 15.

  • links 0, rechts 8 → mitte 4: a[4] = 41 > 15 → rechts = 3
  • links 0, rechts 3 → mitte 1: a[1] = 8 < 15 → links = 2
  • links 2, rechts 3 → mitte 2: a[2] = 15 → gefunden, Index 2

Höchstens ⌈log₂(n + 1)⌉ Schritte, bei 9 Elementen also 4.

Rekursion

Eine Funktion ruft sich selbst auf, bis eine Abbruchbedingung greift.

FUNKTION fak(n)
    WENN n ≤ 1 DANN
        RÜCKGABE 1
    ENDE WENN
    RÜCKGABE n * fak(n - 1)
ENDE FUNKTION

fak(4) = 4 · fak(3) = 4 · 3 · fak(2) = 4 · 3 · 2 · fak(1) = 24, mit 4 Aufrufen. Ruft sich die Funktion zweimal auf (wie fib), zeichne einen Aufrufbaum.

Fehler finden

Spiel den Code mit dem Testfall durch und vergleiche mit dem erwarteten Ergebnis. Typische Fehlerquellen:

  • Schleifengrenzen: BIS n − 1 statt BIS n, Start bei 1 statt 0.
  • Startwerte: max ← 0 scheitert, wenn alle Werte negativ sind.
  • Bedingungen: MOD 2 = 1 (ungerade) statt MOD 2 = 0 (gerade).

Beispielaufgabe mit Lösung

Arrays und Schleifen

Arrays beginnen bei Index 0, laenge(a) ist die Anzahl der Elemente. Das Array a hat einen freien Platz am Ende (0). Welchen Inhalt hat es am Ende, und wie oft wird verschoben?

a ← [15, 23, 61, 66, 69, 0]
wert ← 80
i ← 4
verschoben ← 0
SOLANGE i ≥ 0 UND a[i] > wert
    a[i + 1] ← a[i]
    i ← i - 1
    verschoben ← verschoben + 1
ENDE SOLANGE
a[i + 1] ← wert
AUSGABE a, verschoben
Lösung anzeigen
  • Array am Ende: 15, 23, 61, 66, 69, 80
  • Ausgabe verschoben: 0

Lösungsweg

  1. Alle Werte größer als 80 rücken eine Stelle nach rechts: keiner.
  2. Danach wird 80 an Index 5 eingesetzt.
  3. Ergebnis: [15, 23, 61, 66, 69, 80], 0-mal verschoben.

Oben bekommst du jedes Mal eine neue Aufgabe dieser Art, mit Lösungsweg.