Synthese und Herausforderungen: Kontrollfluss

Was die Einheit erreicht hat

Die Einheit hatte sich vorgenommen, zu lehren, wie man die Ausführungsreihenfolge mit Entscheidungen und Schleifen steuert und wie man über ihre Korrektheit nachdenkt: dass jeder Fall behandelt wird, dass jede Schleife tut, was sie soll, und dass sie terminiert. Dieses Ziel wurde erreicht, gestützt allein auf das, was die Einführung als bekannt vorausgesetzt hat: die Bedingungen der Einheit 3, die Typen der Einheit 2 sowie die Ablaufverfolgung und die Variante der Lektion 1.1. Das Programm, das den größten gemeinsamen Teiler mit drei festen Schritten berechnete und je nach Daten falsch antwortete oder durch null teilte, wurde durch eine dreizeilige Schleife ersetzt, und nun lässt sich beweisen, dass diese Schleife für alle nichtnegativen Daten korrekt ist.

Entscheidungen

Die Lektion Entscheidungen hat die Anweisung if gelehrt, immer mit geschweiften Klammern. Sie hat gezeigt, dass in einer Kette von else if der erste Zweig ausgeführt wird, dessen Bedingung wahr ist, sodass der tatsächliche Fall jedes Zweigs seine Bedingung zusammen mit der Negation aller vorherigen ist; daher kommt es auf die Reihenfolge an, und ein Zweig kann ohne Warnung unerreichbar werden. Sie hat das Korrektheitskriterium jeder Entscheidung aufgestellt: Ihre Fälle müssen disjunkt (das sind sie durch die Form der Kette) und vollständig sein (das sind sie, wenn sie mit else endet), und sie müssen mit denen der Spezifikation übereinstimmen, was man im Inneren jedes Falls und zu beiden Seiten jeder Grenze testet. Sie hat den Bedingungsoperator vorgestellt, um zwischen zwei kurzen Werten ohne eine ganze Entscheidung zu wählen. Sie schloss mit enum class und switch, bei dem der Compiler vor einem vergessenen Fall warnt.

Schleifen

Die Lektion Schleifen hat while, do und for als drei Formen ein und desselben Mechanismus vorgestellt: Das while wertet seine Bedingung vor jedem Durchlauf aus und kann keinen einzigen ausführen; das do führt mindestens einen aus; das for vereint in seinem Kopf die Initialisierung, die Bedingung und die Fortschaltung, und seine Laufvariable lebt nur in der Schleife. Sie hat ihre Äquivalenzen gelehrt, die Ablauftabelle mit $k + 1$ Auswertungen der Bedingung bei $k$ Durchläufen eines while, das durch seine Bedingung endet (und $k$ Auswertungen bei einem do), sowie das Zählen der Durchläufe am Kopf, das dem Off-by-one-Fehler vorbeugt. Sie hat break, continue und die verschachtelten Schleifen hinzugefügt, deren innerer Rumpf so oft ausgeführt wird, wie eine Summe angibt: $m \cdot p$ bei festen Grenzen, $n(n + 1)/2$ beim Dreieck.

Korrekte Schleifen entwerfen

Die Lektion Korrekte Schleifen entwerfen hat die Schleife zu einem Gegenstand des Entwurfs gemacht. Sie hat die Muster zusammengestellt (Zähler, Akkumulator, Maximum und Minimum, Wächter und Flag), jedes bestimmt durch das, was seine Variable nach jedem Durchlauf bedeutet. Sie hat die Invariante definiert, eine Aussage, die jedes Mal gilt, wenn die Bedingung ausgewertet wird, mit ihren drei Pflichten: Initialisierung, Erhaltung und Abschluss, der zusammen mit der falschen Bedingung die Nachbedingung ergibt; und sie hat sie als Induktion über die Anzahl der Durchläufe erkannt. Sie hat gelehrt, rückwärts zu entwerfen, von der Nachbedingung zur Invariante und von der Invariante zum Rumpf. Sie hat die Terminierung mit der Variante begründet und drei Schleifen gezeigt, in denen die Arithmetik von C++ sie entkräftet: die mit Gleitkommawerten, die 1.0 überspringt, den vorzeichenlosen Zähler, der überschlägt, und den vorzeichenbehafteten Zähler, der überläuft. Zuletzt hat sie den ersten Kontakt mit dem Debugger hergestellt.

Numerische Algorithmen

Die Lektion Numerische Algorithmen hat das Vorige auf vier klassische Algorithmen angewandt, die innerhalb von main geschrieben und bewiesen wurden. Die Primalität durch Probedivision, mit dem Satz, dass es genügt, bis $\sqrt{n}$ zu gehen, und mit der Bedingung d <= n / d, die nicht überläuft, wo d * d <= n es tut. Den euklidischen Algorithmus mit der Invariante $\operatorname{ggT}(a, b) = \operatorname{ggT}(a_0, b_0)$ und der Variante $b$ und seine zwei Gefahren in C++: das negative Ergebnis und die Division durch null, wenn die Bedingung nach dem Rumpf ausgewertet wird. Den Basiswechsel durch fortgesetzte Division und das Horner-Schema, das ein Polynom mit einer Multiplikation pro Koeffizient auswertet. Und die Bisektion, garantiert durch den Zwischenwertsatz und gesteuert von einem ganzzahligen Zähler, dessen Anzahl an Durchläufen man im Voraus berechnet.