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.
Deine 3 kostenlosen Aufgaben in „Algorithmen“ sind gelöst
Die Erklärung weiter unten bleibt frei, und in jedem anderen Thema kannst du ebenfalls drei Aufgaben kostenlos lösen.
Dein AP1-Zugang gilt für die AP1-Themen. „Algorithmen“ gehört zur AP2-Vorbereitung.
Unbegrenzt neue Aufgaben in allen 34 Themen, AP1 und AP2
Gemischt üben mit AP1- und AP2-Themen
Fortschritt im Konto, auf jedem Gerät
49 € einmalig für 6 Monate.39 € statt 49 €, weil du den AP1-Zugang gekauft hast. Kein Abo, keine automatische Verlängerung.
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.
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
Alle Werte größer als 80 rücken eine Stelle nach rechts: keiner.