Übung — AFB III (Verallgemeinern und Reflektieren)

Musterlösung: Betrachtet wird der Wert von a. Die Schleife läuft nur, solange a ≥ b gilt; im Rumpf wird a ← a − b ausgeführt. Wegen b ≥ 1 ist a danach um mindestens 1 kleiner als vorher, und wegen a ≥ b ist der neue Wert a − b ≥ 0. Der Wert von a ist also vor jedem Durchlauf eine natürliche Zahl, die bei jedem Durchlauf echt kleiner wird. Eine natürliche Zahl kann nur endlich oft verkleinert werden, ohne negativ zu werden — spätestens nach a Durchläufen ist die Bedingung a ≥ b falsch, und der Algorithmus hält an.

Bei b = 0 lautet die Bedingung a ≥ 0; sie ist für jede natürliche Zahl wahr. Im Rumpf wird a ← a − 0 gerechnet, a ändert sich also nie: Der Algorithmus terminiert nicht. Er ist deshalb nur mit der Vorbedingung b ≥ 1 korrekt; eine robuste Fassung prüft vorher wenn b = 0 dann Ausgabe: „Division durch 0“.

Der Algorithmus zieht b so oft ab, wie es geht — die Anzahl der Durchläufe ist a / b, die Ausgabe ist der Rest a mod b. Beispiel: a = 23, b = 4 liefert nach 5 Durchläufen die Ausgabe 3.

Musterlösung: Gegenbeispiel j = 1900: Es gilt 1900 mod 4 = 0, die Operation gibt also wahr zurück. Da aber auch 1900 mod 100 = 0 und 1900 mod 400 = 300 ≠ 0 gilt, war 1900 nach der Kalenderregel kein Schaltjahr. Damit ist die Operation nicht korrekt (genauso versagt sie für 1800 oder 2100).

Die Tests mit 2000 und 2024 liefern trotzdem das richtige Ergebnis: 2024 ist nicht durch 100 teilbar, dort gilt die einfache Regel; 2000 ist durch 400 teilbar und damit tatsächlich ein Schaltjahr. Zwischen 1901 und 2099 stimmt die fehlerhafte Operation sogar für jedes Jahr — erfolgreiche Tests beweisen eben keine Korrektheit, sie zeigen nur, dass für die getesteten Eingaben kein Fehler auftritt.

Korrigierte Fassung:

Operation istSchaltjahr(j)
  wenn j mod 400 = 0 dann
    zurück wahr
  ende wenn
  wenn j mod 100 = 0 dann
    zurück falsch
  ende wenn
  zurück j mod 4 = 0

static boolean istSchaltjahr(int j) {
    return (j % 4 == 0 && j % 100 != 0) || j % 400 == 0;
}

Die Bedingungen werden vom speziellsten Fall (400) zum allgemeinsten (4) geprüft; weil zurück die Operation sofort beendet, erreicht ein durch 400 teilbares Jahr die Prüfung auf 100 gar nicht erst.

Operation quersumme(n)
  s ← 0
  solange n > 0 wiederhole
    s ← s + n mod 10
    n ← n / 10
  ende solange
  zurück s

static int quersumme(int n) {
    int s = 0;
    while (n > 0) {
        s = s + n % 10;
        n = n / 10;
    }
    return s;
}

Musterlösung: Die Variable s ist ein Akkumulator, der die Ziffern aufsammelt. In jedem Durchlauf wird mit n mod 10 die letzte Ziffer addiert und mit der Ganzzahldivision n / 10 abgeschnitten. Für n = 40953 werden nacheinander die Ziffern 3, 5, 9, 0, 4 addiert; danach ist n = 0 und die Operation gibt 21 zurück.

Terminierung: Solange n > 0 ist, gilt n / 10 < n, der Wert von n wird also in jedem Durchlauf echt kleiner und bleibt dabei eine natürliche Zahl. Nach so vielen Durchläufen, wie n Stellen hat, ist n = 0 und die Bedingung falsch. Randfall n = 0: Die Schleife läuft gar nicht, zurückgegeben wird der Startwert 0 — und das ist die richtige Quersumme von 0.

Operation istPalindrom(s)
  i ← 0
  j ← länge(s) − 1
  solange i < j wiederhole
    wenn s[i] ≠ s[j] dann
      zurück falsch
    ende wenn
    i ← i + 1
    j ← j − 1
  ende solange
  zurück wahr

static boolean istPalindrom(String s) {
    int i = 0;
    int j = s.length() - 1;
    while (i < j) {
        if (s.charAt(i) != s.charAt(j)) {
            return false;
        }
        i++;
        j--;
    }
    return true;
}

Musterlösung: Die Operation vergleicht das erste mit dem letzten Zeichen, das zweite mit dem vorletzten usw. Sobald zwei Zeichen verschieden sind, steht fest, dass s kein Palindrom ist, und zurück falsch beendet die Operation. Treffen sich i und j (oder überholen sich), wurden alle Paare erfolgreich verglichen, und es wird wahr zurückgegeben. Bei ungerader Länge bleibt das mittlere Zeichen unverglichen — es steht ja auf beiden Seiten an derselben Stelle. Randfälle: Für die leere Zeichenkette und für ein einzelnes Zeichen gilt von Anfang an i ≥ j, die Operation liefert wahr, was der Definition entspricht.

Beurteilung „Rentner“: Verglichen werden die Zeichencodes. 'R' hat den ASCII-Wert 82, 'r' den Wert 114 — die Zeichen sind also verschieden, obwohl ein Mensch das Wort als Palindrom erkennt. Abhilfe: Die Zeichenkette vor der Prüfung einheitlich in Kleinbuchstaben umwandeln (Java s.toLowerCase(), Python s.lower()) oder beim Vergleich Großbuchstaben (65–90) durch Addition von 32 in Kleinbuchstaben umrechnen.

Operation istPrim(n)
  wenn n < 2 dann
    zurück falsch
  ende wenn
  t ← 2
  solange t · t ≤ n wiederhole
    wenn n mod t = 0 dann
      zurück falsch
    ende wenn
    t ← t + 1
  ende solange
  zurück wahr

Musterlösung: Zahlen kleiner als 2 sind keine Primzahlen und werden sofort abgewiesen. Danach werden mögliche Teiler t ab 2 durchprobiert; findet sich einer mit n mod t = 0, ist n zusammengesetzt und die Operation endet mit falsch. Findet sich keiner, ist n eine Primzahl. Für n = 2 und n = 3 ist schon 2 · 2 > n, die Schleife läuft nicht, und es wird richtig wahr zurückgegeben.

Begründung der Grenze: Ist n zusammengesetzt, lässt es sich als n = t · u mit 2 ≤ t ≤ u schreiben. Dann gilt t · t ≤ t · u = n. Der kleinere Faktor eines jeden Teilerpaares erfüllt also t · t ≤ n und wird von der Schleife gefunden (bei 91 = 7 · 13 etwa schon bei t = 7, weil 7 · 7 = 49 ≤ 91). Gibt es bis zu dieser Grenze keinen Teiler, gibt es auch darüber keinen. Die Schleife terminiert, weil t in jedem Durchlauf um 1 wächst, t · t also irgendwann größer als n wird.

Für n = 97 werden t = 2, 3, …, 9 getestet (9 · 9 = 81 ≤ 97, aber 10 · 10 = 100 > 97) — das sind 8 Tests statt 95 bei der Suche bis n − 1.

Musterlösung: Der erste Aufruf liefert zufällig das richtige Ergebnis: summe ist 0, wird auf 12 erhöht, und 12 / 3.0 = 4,0. Beim zweiten Aufruf steht in der globalen Variable aber noch 12; sie wird auf 15 erhöht, und ausgegeben wird 5,0 statt 1,0. Die Operation hat einen Seiteneffekt: Sie verändert eine globale Variable, sodass ihr Ergebnis nicht nur von den Parametern, sondern von allen früheren Aufrufen abhängt. Das macht Fehler schwer zu finden, weil derselbe Aufruf je nach Vorgeschichte verschiedene Werte liefert.

static double mittelwert(int a, int b, int c) {
    int summe = a + b + c;   // lokal: bei jedem Aufruf neu
    return summe / 3.0;
}

In der verbesserten Fassung ist summe lokal: Die Daten kommen über die Parameter hinein und über return heraus, jeder Aufruf ist unabhängig. Eine globale Variable ist nur dann sinnvoll, wenn ein Wert absichtlich über mehrere Aufrufe hinweg erhalten bleiben soll, etwa die Anzahl aller bisher berechneten Mittelwerte. Auch dann sollte nur eine klar benannte Operation sie verändern.

Musterlösung: Beim Aufruf werden die Argumente der Reihe nach in die Parameter kopiert — die Namen der Variablen im Hauptprogramm spielen dabei keine Rolle. Der Aufruf potenz(exponent, basis) bewirkt also: Parameter basis ← Wert von exponent = 2 und Parameter exponent ← Wert von basis = 5. Die Schleife multipliziert fünfmal mit 2, ausgegeben wird 2⁵ = 32 und nicht 25. Damit ist die Behauptung widerlegt; korrekt wäre der Aufruf potenz(basis, exponent).

Der Test mit potenz(2, 4) und potenz(4, 2) ergibt in beiden Fällen 16, weil zufällig 2⁴ = 4² gilt. Wer nur diese beiden Aufrufe vergleicht, hält die Reihenfolge fälschlich für egal. Ohne Bedeutung ist die Reihenfolge nur bei symmetrischen Operationen wie einer Summe oder einem Produkt zweier Zahlen — oder wenn beide Argumente denselben Wert haben.

Musterlösung: Zeichenketten werden lexikographisch verglichen: Das erste Zeichen, in dem sich zwei Ketten unterscheiden, entscheidet nach seinem ASCII-Wert. Bei "100" und "25" sind das schon die ersten Zeichen: '1' (49) ist kleiner als '2' (50), also steht "100" vorn — obwohl die Zahl 100 größer ist als 25. Ziffern (48–57) haben kleinere Codes als alle Buchstaben, deshalb stehen beide Zahlen am Anfang. "Apfelmus" kommt vor "Birne", weil 'A' (65) < 'B' (66). "apfel" steht hinten, weil der Kleinbuchstabe 'a' den Code 97 hat und damit größer ist als jeder Großbuchstabe (65–90).

Beurteilung: Vergleicht man s.toLowerCase().compareTo(t.toLowerCase()), entsteht "100", "25", "apfel", "Apfelmus", "Birne": Groß- und Kleinschreibung stören nicht mehr, und "apfel" steht als Präfix von "Apfelmus" richtig davor. Das Problem mit den Zahlen bleibt aber bestehen, denn die Ziffern ändern sich beim Umwandeln nicht. Dafür müsste man Zahlen vorher in int umwandeln (Integer.parseInt) und als Zahlen vergleichen. Der Vorschlag ist also eine Verbesserung, aber keine vollständige Lösung.

Musterlösung: Variante A: Math.random() * 6 liegt im Bereich [0; 6). Das Abschneiden mit (int) liefert die ganzen Zahlen 0 bis 5, nach Abzug von 3 also −3 bis 2. Der Wert +3 kommt nie vor — die Anforderung ist verletzt.

Variante B: Durch das Runden entstehen die Werte 0 bis 6, nach Abzug von 3 tatsächlich −3 bis +3. Die Werte sind aber nicht gleich wahrscheinlich: Auf 0 wird nur aus dem Intervall [0; 0,5) gerundet, auf 6 nur aus [5,5; 6) — das sind jeweils Intervalle der Breite 0,5, während jeder innere Wert ein Intervall der Breite 1 hat. −3 und +3 treten daher nur mit Wahrscheinlichkeit 1/12 auf, die übrigen Werte mit 1/6. Auch Variante B erfüllt die Anforderung nicht.

Korrekt: Von −3 bis +3 gibt es b − a + 1 = 3 − (−3) + 1 = 7 Werte, also muss mit 7 multipliziert und abgeschnitten werden:

int z = (int) (Math.random() * 7) - 3;   // −3 … 3, alle mit Wahrscheinlichkeit 1/7

import random
z = random.randint(-3, 3)   # beide Grenzen gehören dazu

Musterlösung: Das Struktogramm enthält eine kopfgesteuerte Schleife: Die Bedingung n > 1 wird vor jedem Durchlauf geprüft. Der Java-Code verwendet dagegen eine fußgesteuerte do-while-Schleife, deren Rumpf mindestens einmal ausgeführt wird. Für jede Eingabe n ≥ 2 ist die Bedingung vor dem ersten Durchlauf wahr; dann laufen beide Fassungen identisch (für n = 6 zum Beispiel beide mit der Ausgabe 8). Für n = 1 dagegen führt das Struktogramm keinen Durchlauf aus und gibt 0 aus, während der Java-Code 1 → 4 → 2 → 1 rechnet und 3 ausgibt. Die Umsetzung ist also nicht korrekt, der Fehler zeigt sich nur beim Randfall n = 1.

int t = 0;
while (n > 1) {
    if (n % 2 == 0) {
        n = n / 2;
    } else {
        n = 3 * n + 1;
    }
    t++;
}
System.out.println(t);

Anmerkung: Dass die Schleife für jedes n ≥ 1 terminiert, ist übrigens bis heute nicht bewiesen (Collatz-Vermutung) — ausprobiert wurde es nur für sehr viele, aber endlich viele Zahlen. Ein Terminierungsbeweis wie in Aufgabe 1 gelingt hier nicht, weil n nicht in jedem Durchlauf kleiner wird.