Algorithmen darstellen
Ein Algorithmus ist eine genaue Handlungsvorschrift. Ob in Worten, als Pseudocode, als Struktogramm oder als Java- und Python-Quelltext — alle vier Darstellungen beschreiben denselben Ablauf, und jeder davon besteht aus nur drei Bausteinen.
Algorithmus
Endliche Folge eindeutiger, ausführbarer Anweisungen. Stolperstein: „endlich“ betrifft die Beschreibung, „terminiert“ den Ablauf.
Drei Bausteine
Sequenz (nacheinander), Verzweigung (Bedingung entscheidet) und Wiederholung (Schleife). Sie dürfen ineinander geschachtelt werden.
wenn … dann … sonstsolange … wiederholeStruktogramm
Kastenformen von oben nach unten gelesen. Kopfgesteuerte Schleife: Bedingung oben; fußgesteuert: Bedingung unten.
Analysieren
Rolle jeder Variablen bestimmen, mit kleinen Werten durchspielen, dann in einem Satz sagen, was berechnet wird.
z ← z + 1Akkumulator
s ← s + x< oder ≤ — ein Durchlauf Unterschied
Ob die Bedingung i < n oder i ≤ n heißt, entscheidet über einen Durchlauf mehr oder weniger. Und eine Bedingung mit ≠ ist gefährlich: Springt die Variable über den Abbruchwert hinweg, terminiert die Schleife nie.
Variablen und Operationen
Variablen speichern die Zwischenstände eines Algorithmus, Operationen verpacken Teilalgorithmen unter einem Namen. Mit einer Tracetabelle verfolgst du beides Schritt für Schritt.
Variable und Zuweisung
Name + Datentyp + Wert. Die Zuweisung wertet erst rechts aus und speichert dann links — der alte Wert ist danach verloren.
x ← x + 1Java/Python:
x = x + 1Datentypen
Ganze Zahl, Kommazahl (mit Punkt!), Wahrheitswert, einzelnes Zeichen, Zeichenkette. (int) 2.9 schneidet ab: 2.
int · double · boolean · char · StringTracetabelle
Eine Spalte je Variable, eine Zeile je Schritt; eingetragen wird nur, was sich ändert — auch die letzte Prüfung, die falsch ergibt.
Lokal und global
Lokale Variablen und Parameter gelten nur in ihrer Operation und verschwinden nach dem Aufruf. Gleicher Name: die lokale verdeckt die globale.
this.punktePython:
global punkteint maximum(int x, int y); zurück bzw. return beendet die Operation und liefert den Wert, der den Aufruf ersetzt.Ausgabe ist keine Rückgabe
System.out.println(x) bzw. print(x) zeigt einen Wert nur an. Weiterrechnen kann der Aufrufer nur mit einem Wert, der per return zurückkommt — eine void-Methode liefert keinen.
Mit Zahlen und Zeichen arbeiten
Ganzzahldivision und Rest zerlegen Zahlen, Zufallszahlen bringen Abwechslung. Zeichenketten sind Reihen von Zeichen mit Positionen ab 0 — und jedes Zeichen ist für den Computer eine Zahl.
Division und Rest
Wie oft passt b ganz in a, und was bleibt übrig? Letzte Ziffer: x mod 10; gerade: x mod 2 = 0.
17 / 5 = 3 · 17 mod 5 = 2Python:
17 // 5 · 17 % 5Zufallszahlen
Math.random() liegt in [0; 1). Mal Anzahl, abschneiden, Startwert addieren.
(int) (Math.random() * 6) + 1random.randint(1, 6)Zeichenketten
Index von 0 bis länge − 1. Die Teilzeichenkette von a bis b endet vor b und hat b − a Zeichen.
s.charAt(i) · s.substring(a, b)s[i] · s[a:b]ASCII und Vergleich
'0' = 48, 'A' = 65, 'a' = 97. Beim Vergleich entscheidet das erste unterschiedliche Zeichen.
s.equals(t) · s.compareTo(t)ord(c) · chr(n)/ die Ganzzahldivision und der Rest liegt immer zwischen 0 und b − 1. Beispiel: 17 − 3 · 5 = 2.Java und Python rechnen verschieden
Python: / ist immer Kommadivision, ganzzahlig teilt //. Bei negativen Zahlen liefert Java -7 % 3 = −1, Python 2 — im Abitur meint mod den kleinsten positiven Rest, also 2.
Die Regeln, an denen die Punkte hängen
Die meisten Punkte gehen in diesem Kapitel nicht an einer schweren Idee verloren, sondern an einer Grenze, die um eins daneben liegt, an einer Anweisung an der falschen Stelle oder an einem Wert, der nie zurückkommt. Diese drei Regeln fangen fast alles davon ab.
Regel 1: Grenzen genau prüfen
Zählen beginnt bei 0, der letzte Index ist länge − 1, deshalb i < s.length(). substring(a, b) endet vor b. Spiele jede Schleife mit einem kleinen Randfall in einer Tracetabelle durch — dann fällt ein Durchlauf zu viel oder zu wenig sofort auf.
Regel 2: Vor, in und nach der Schleife
Startwerte stehen vor der Schleife, die Änderung der Bedingungsvariable steht im Rumpf, die Ausgabe des Ergebnisses steht nach der Schleife. Wer das im Struktogramm an der Einrückung sauber zeigt, verliert hier keine Punkte.
Regel 3: Werte hinein, Werte heraus
Daten gehen über Parameter in eine Operation — in der Reihenfolge des Kopfes — und über zurück/return wieder heraus. Lokale Variablen gibt es nach dem Aufruf nicht mehr, und ein print ersetzt keine Rückgabe.