Zum Inhalt springen
Topos Uranos
Deutsch

Schleifen

Zusammenfassung

Die Lektion Vom Problem zum Algorithmus hat drei Arten erkannt, Schritte zusammenzusetzen: die Sequenz, die Entscheidung und die Wiederholung. Die ersten beiden haben in C++ bereits ihre Schreibweise; diese Lektion gibt der dritten die ihre. Sie behandelt die drei Formen der Schleife: while, die ihre Bedingung vor jedem Durchlauf auswertet und ihren Rumpf womöglich nie ausführt; do, die sie danach auswertet und den Rumpf mindestens einmal ausführt; und for, die in einer Zeile die Initialisierung, die Bedingung und die Fortschaltung der Variablen vereint, die die Wiederholung steuert. Sie zeigt, dass die drei ein und denselben Mechanismus ausdrücken, sodass sich jede in die anderen umformen lässt, und lehrt, die klarste zu wählen; sie stellt break und continue vor, die den Verlauf eines Durchlaufs verändern; und sie schließt mit den verschachtelten Schleifen, deren innerer Rumpf so oft ausgeführt wird, wie sich mit einer Summe berechnen lässt. Das Werkzeug, das die ganze Lektion begleitet, ist die Ablauftabelle: eine Schleife von Hand Durchlauf für Durchlauf nachzuvollziehen ist der Weg, vorherzusagen, wie oft ihr Rumpf ausgeführt wird und was sie beim Verlassen hinterlässt.

Lernziele

  1. Eine while-, do- oder for-Schleife für eine gegebene Wiederholung schreiben und dabei die klarste Form wählen.
  2. Eine Schleife mit ihrer Ablauftabelle von Hand nachvollziehen und vorhersagen, wie oft der Rumpf ausgeführt wird.
  3. Eine Schleife von einer Form in eine andere umformen, ohne ihre Bedeutung zu ändern.
  4. Verschachtelte Schleifen schreiben und berechnen, wie oft der innere Rumpf ausgeführt wird.

while

Die Form einer while-Schleife

Eine while-Schleife schreibt man so:

C++-Code
while (Bedingung) {    Rumpf}

Ihre Bedeutung lässt sich in drei Schritten angeben: Die Bedingung wird ausgewertet; ist sie falsch, endet die Schleife, und die Ausführung geht nach der schließenden geschweiften Klammer weiter; ist sie wahr, wird der Rumpf ausgeführt und zum ersten Schritt zurückgekehrt. Jede Ausführung des Rumpfes heißt ein Durchlauf (oder eine Iteration). Die Bedingung ist ein boolescher Ausdruck wie die aus der Lektion Relationen und Logik, und der Rumpf ist ein Block; die Regel der geschweiften Klammern, die die Lektion Entscheidungen festgelegt hat, gilt auch hier: Der Rumpf einer Schleife steht immer in geschweiften Klammern, auch wenn er nur eine einzige Anweisung enthält.

Aus der Definition folgen zwei Konsequenzen. Die erste: Die Bedingung wird vor jedem Durchlauf ausgewertet, sodass der Rumpf kein einziges Mal ausgeführt wird, wenn sie von Anfang an falsch ist. Die zweite: Damit die Schleife endet, muss der Rumpf etwas von dem ändern, was die Bedingung liest; ändert sich nichts, so bleibt eine Bedingung, die einmal wahr war, für immer wahr. Nun genügt Ändern nicht: Die Lektion Vom Problem zum Algorithmus hat gezeigt, dass eine natürliche Größe nötig ist, die in jedem Durchlauf abnimmt, die Variante, und die Lektion Korrekte Schleifen entwerfen wird daraus eine Methode machen.

Die Division durch fortgesetzte Subtraktion

Der erste Algorithmus mit Wiederholung im Kurs war die Division durch fortgesetzte Subtraktion: Solange der Rest mindestens so groß wie der Divisor ist, wird von ihm der Divisor abgezogen und zum Quotienten eins addiert. In C++ geschrieben, lässt sich der Algorithmus fast Wort für Wort übertragen.

BeispielQuotient und Rest durch Subtraktion
C++-Programm
#include <iostream>#include <print>​int main(){    int a{};    int b{};    std::cin >> a >> b;    int q{0};    int r{a};    while (r >= b) {        r -= b;        ++q;    }    std::println("{} = {} · {} + {}", a, b, q, r);}
Programmeingabe
23 7
Ausgabe
23 = 7 · 3 + 2

Die Zeilen 9 und 10 geben den Variablen ihren Anfangswert: Noch ist nichts abgezogen worden, sodass der Quotient 0 ist und der Rest der ganze Dividend. Zeile 11 ist die Bedingung von Schritt 2 des Algorithmus; die Zeilen 12 und 13 sind der Rumpf. Das Programm setzt wie der Algorithmus voraus, dass a≥0a \geq 0 und b>0b > 0 gilt: Mit b=0b = 0 würde Zeile 12 r nicht ändern, und die Schleife würde nicht enden.

Die Ablauftabelle

Die Schleife von Hand nachzuvollziehen heißt, eine Tabelle auszufüllen: eine Zeile pro Durchlauf, eine Spalte pro Variable und eine für die Bedingung, ausgewertet zu Beginn des Durchlaufs. Zeile 0 hält den Zustand vor der ersten Auswertung fest; die letzte Zeile die Auswertung, die falsch ausfällt und die Schleife beendet.

BeispielDer Ablauf von 23 durch 7

Beweis

  1. Vor der Schleife werden die Zeilen 9 und 10 ausgeführt: q=0q = 0 und r=23r = 23. Das ist Zeile 0 der Tabelle; die Bedingung ist noch nicht ausgewertet worden.

  2. Erster Durchlauf. Die Bedingung 23≥723 \geq 7 ist wahr, also wird der Rumpf ausgeführt: rr wird zu 16 und qq zu 1. Danach kehrt die Ausführung zu Zeile 11 zurück.

  3. Zweiter Durchlauf. 16≥716 \geq 7 ist wahr: rr wird zu 9 und qq zu 2.

  4. Dritter Durchlauf. 9≥79 \geq 7 ist wahr: rr wird zu 2 und qq zu 3.

  5. Die vierte Auswertung, 2≥72 \geq 7, ist falsch: Der Rumpf wird nicht ausgeführt, die Schleife endet, und Zeile 15 gibt 23=7⋅3+223 = 7 \cdot 3 + 2 aus.

Der Ablauf lehrt das Zählen. Der Rumpf wurde dreimal ausgeführt, so oft wie der Quotient angibt, und die Bedingung wurde viermal ausgewertet: einmal pro Durchlauf und einmal mehr, nämlich die Auswertung, die fehlschlägt. Diese Beziehung gilt für jede while-Schleife, die durch ihre Bedingung endet: Wird der Rumpf kk-mal ausgeführt, so wird die Bedingung k+1k + 1-mal ausgewertet. Und der Extremfall bestätigt es: Mit der Eingabe 5 7 ist die erste Auswertung, 5≥75 \geq 7, schon falsch, der Rumpf wird nullmal ausgeführt, und das Programm gibt 5=7⋅0+55 = 7 \cdot 0 + 5 aus, was richtig ist. Eine gut geschriebene while-Schleife behandelt ohne zusätzlichen Code den Fall, in dem es nichts zu wiederholen gibt.