Aufgabenblock — AFB III
Begründen statt nur ausführen: Terminierung beweisen, Gegenbeispiele finden, eigene Operationen entwerfen und fremden Code beurteilen. Formuliere deine Antwort erst selbst — in ganzen Sätzen oder als Pseudocode —, bevor du die Musterlösung aufklappst.
Beweisen Sie, dass der folgende Algorithmus für alle natürlichen Zahlen a ≥ 0 und b ≥ 1 nach endlich vielen Schritten anhält. Beurteilen Sie außerdem, was bei der Eingabe b = 0 geschieht, und geben Sie an, was der Algorithmus berechnet.
Eingabe: a, b solange a ≥ b wiederhole a ← a − b ende solange Ausgabe: a
Hinweis: Suche eine Größe, die in jedem Schleifendurchlauf echt kleiner wird, aber nicht beliebig klein werden kann.
Musterlösung anzeigen (zählt als erledigt)
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.
Nach dem gregorianischen Kalender ist ein Jahr ein Schaltjahr, wenn seine Jahreszahl durch 4 teilbar ist — außer sie ist durch 100 teilbar; durch 400 teilbare Jahre sind aber wieder Schaltjahre. Eine Schülerin implementiert:
Operation istSchaltjahr(j) wenn j mod 4 = 0 dann zurück wahr sonst zurück falsch ende wenn
Widerlegen Sie die Korrektheit dieser Operation mit einem Gegenbeispiel, begründen Sie, warum Tests mit den Jahren 2000 und 2024 den Fehler nicht aufdecken, und entwerfen Sie eine korrigierte Fassung.
Hinweis: Welche Jahre behandelt die Kalenderregel anders als die einfache Regel „durch 4 teilbar“?
Musterlösung anzeigen (zählt als erledigt)
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.
Entwerfen Sie eine Operation quersumme(n), die für eine natürliche Zahl n die Summe ihrer Ziffern zurückgibt, z. B. quersumme(40953) = 4 + 0 + 9 + 5 + 3 = 21. Verwenden Sie dabei keine Zeichenketten, sondern nur / und mod. Begründen Sie anschließend, dass Ihre Schleife für jedes n ≥ 0 terminiert und dass auch n = 0 richtig behandelt wird.
Hinweis: Welche Ziffer einer Zahl erhältst du mit einer einzigen Rechnung — und wie wirst du sie danach los?
n mod 10 liefert die letzte Ziffer, n / 10 schneidet sie ab. Sammle die Ziffern in einem Akkumulator.Warum so? Die letzte Ziffer ist die einzige, die man ohne Kenntnis der Stellenzahl direkt „greifen“ kann. Wiederholt man das, kommen alle Ziffern der Reihe nach an die letzte Stelle.Musterlösung anzeigen (zählt als erledigt)
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.