3 Schleifen

Zum vorigen Kapitel Zum Inhaltsverzeichnis Zum nächsten Kapitel


In diesem Abschnitt wird die letzte noch ausstehende sprachlogische Grundstruktur erarbeitet, nämlich die Schleife. Zur Erinnerung ist hier nochmals das Struktogramm der Schleife abgebildet:



In Delphi wird diese Programmstruktur in Form der REPEAT..UNTIL..-Anweisung zur Verfügung gestellt:
        REPEAT
          Anweisung
        UNTIL Bedingung;
Dabei wird die Anweisung so lange wiederholt, bis die Bedingung erfüllt ist. Die Bedingung ist also eine Abbruchbedingung. Damit die Schleife nicht endlos wiederholt wird, muss im "Schleifenkörper" (d.h. zwischen "REPEAT" und "UNTIL"} wenigstens eine Anweisung stehen, die die Schleifen-Bedingung beeinflußt.

Eine Besonderheit der REPEAT-UNTIL-Schleife von Pascal ist, dass der Schleifenkörper auch aus mehreren Anweisungen bestehen darf, also eine ganze Sequenz sein kann, ohne dass eine Klammerung mit "begin" und "end" nötig wäre:
        REPEAT
          Anweisung_1
          Anweisung_2
          ....
          ....
          Anweisung_n
        UNTIL Bedingung;
In Java wird diese Programmstruktur in Form der do..while..-Anweisung zur Verfügung gestellt:
        do {
          Anweisung_1
          Anweisung_2
          .............
          Anweisung_n
        } while (Bedingung);
Dabei werden die Anweisungen so lange wiederholt, wie die Bedingung erfüllt ist. Die Bedingung ist also eine Durchführungsbedingung. Damit die Schleife nicht endlos wiederholt wird, muss im "Schleifenkörper" (d.h. zwischen "do" und "while") wenigstens eine Anweisung stehen, die die Schleifen-Bedingung beeinflußt.

Wenn Sie tatsächlich mal eine do..while..-Schleife haben sollten, deren Anweisungsblock nur eine einzige Anweisung enthält, dann könnten Sie die geschweiften Klammern um den Block weglassen. Dieser Fall wird allerdings so selten eintreten, dass Sie in aller Regel die blockbildenden Klammern lieber stehen lassen sollten.

Als Beispiel wollen wir die Multiplikation zweier Zahlen als wiederholte Addition programmieren: "3 * 5" wird berechnet, indem man zur Null dreimal die 5 addiert.
In Delphi könnte der entsprechende algorithmische Kern etwa so aussehen:
     procedure TForm1.Button1Click(Sender: TObject);
       var e, s, z : Integer;    { Lokale Variablen }
       begin
       { Eingabe }
       z := StrToInt(Edit1.Text);
       s := StrToInt(Edit2.Text);

       { Verarbeitung }
       e := 0;
       Repeat
         e := e + s;
         z := z - 1;
       until z <= 0;   { Abbruchbedingung }

       { Ausgabe }
       Edit3.Text := IntToStr(e);
       end;
In Java könnte der algorithmische Kern etwa so aussehen:
     public void button1_ActionPerformed(ActionEvent evt) {
       /* Eingabe */
       int z = Integer.parseInt(textField1.getText());
       int s = Integer.parseInt(textField2.getText());
       int e = 0;

       /* Verarbeitung */
       do {
         e = e + s;
         z = z - 1;  { }
       } while (z > 0);  /* Durchführungsbedingung */

       /* Ausgabe */
       textField3.setText(Integer.toString(e));
     }
Die eigentlichen Rechenschritte werden also mit den lokalen Variablen e, s und z ausgeführt. Das Herunterzählen der Variablen z führt dazu, dass die Schleife schließlich verlassen wird. Der angegebene Algorithmus liefert für nicht zu große natürliche Zahlen korrekte Ergebnisse.


Übungen:


  1. Multiplizieren durch Addieren:

    1. Schreiben Sie das Programm zur "Multiplikation durch wiederholte Addition". Verwenden Sie die oben angegebene Klick-Prozedur für den "Berechnen"-Knopf.

    2. Überzeugen Sie sich, dass das Programm für positive ganze Zahlen richtig funktioniert. Warum steht oben so vorsichtig "...nicht zu große..." Zahlen? Versuchen Sie herauszubekommen, in welchem Bereich das Programm korrekt rechnet.

    3. Das Programm kann zwar "7 * 0" korrekt berechnen, aber nicht "0 * 7". Machen Sie sich klar, woran das liegt!

    Lösungsvorschlag: [Delphi] [Java]



  2. Dividieren durch Subtrahieren:

    Analog zum Algorithmus der vorigen Aufgabe kann man auch die Frage beantworten, wie oft eine natürliche Zahl b in einer Zahl a enthalten ist. Diese mathematische Operation wird "Ganzzahl-Division" genannt und mit "a DIV b" abgekürzt. Z.B. ist 17 DIV 3 = 5, weil in 17 die 3 genau 5 mal ganz enthalten ist.

    1. Schreiben Sie ein Programm zur Berechnung von a DIV b mit Hilfe einer subtrahierenden Schleife. Subtrahieren Sie dazu von a die Zahl b so oft, bis a kleiner als b geworden ist, und zählen Sie dabei die Subtraktionsschritte.

    2. Das Programm funktioniert nicht für alle Kombinationen positiver Zahlen korrekt. Unter welchen Bedingungen liefert es falsche Ergebnisse?

    Lösungsvorschlag: [Delphi] [Java]




Wenn Sie herausgefunden haben, wann Ihr Programm den Wert von a DIV b falsch berechnet, werden Sie sich für die kritischen Fälle wünschen, dass die Anweisungen eines Schleifenkörpers erst nach der Prüfung einer Bedingung ausgeführt würden. Das folgende Struktogramm stellt eine solche Schleife dar:



Hier wird also zuerst geprüft, ob die Bedingung erfüllt ist, bevor die Anweisungen des Schleifenkörpers ausgeführt werden.
In Delphi ist diese Schleife durch die WHILE..DO..-Anweisung realisiert:
        WHILE Bedingung DO
          Anweisung;
Solange die Bedingung erfüllt ist, wird die Anweisung ausgeführt. Man beachte, dass die Bedingung hier eine Durchführungsbedingung ist, im Gegensatz zur Repeat-Schleife, bei der eine Abbruchbedingung vorliegt. Es gibt noch einen anderen Unterschied: wenn der Schleifenkörper der While-Schleife mehrere Anweisungen enthalten soll, dann müssen diese mit BEGIN....END "geklammert" werden:
   WHILE Bedingung DO BEGIN
     Anweisung_1;
     Anweisung_2;
      .....
     Anweisung_n;
     END;
Bei allen Unterschieden zwischen den beiden Schleifenarten gibt es aber auch Gemeinsames: damit die Schleife nicht endlos wiederholt wird, muss auch im Schleifenkörper der While-Schleife (d.h. zwischen "DO BEGIN" und "END;"} wenigstens eine Anweisung stehen, die die Schleifen-Bedingung beeinflußt.

Der wesentliche Unterschied zur "REPEAT..UNTIL.."-Schleife ist, dass die Bedingung bei jener erst nach dem ersten Durcharbeiten des Schleifenblocks getestet wird, bei der "WHILE..DO.."-Schleife jedoch schon vor diesem ersten Durchlauf. Mithin gilt für die Anzahl n der Durchläufe des Anweisungsblocks bei einer "REPEAT..UNTIL.."-Schleife die Ungleichung "n >= 1", während bei der "WHILE..DO.."-Schleife gilt "n >= 0". Das mag Ihnen als ein eher kleiner Unterschied erscheinen, kann aber beim Programmieren weitreichende und gelegentlich auch katastrophale Folgen haben.
In Java ist diese Schleife durch die while...-Anweisung realisiert:
   while (Bedingung) {
     Anweisung_1;
     Anweisung_2;
      .....
     Anweisung_n;
   }
Solange die Bedingung erfüllt ist, werden die Anweisungen ausgeführt. Man beachte, dass auch hier die Bedingung eine Durchführungsbedingung ist.

Damit die Schleife nicht endlos wiederholt wird, muss auch im Schleifenkörper der while-Schleife wenigstens eine Anweisung stehen, die die Schleifen-Bedingung beeinflusst. Deshalb folgt nach der Bedingung gleich ein ganzer Block, der mit { und } geklammert ist. Der Fall, dass Sie diese Klammern weglassen können, weil der Schleifenkörper nur 1 Anweisung enthält, wird in der Praxis so selten auftauchen, dass Sie sich ohne Schaden angewöhnen können, die Blockmarkierungen grundsätzlich stehen zu lassen - so wie sie von vielen Java-Editoren ja schon während der Eingabe vorausschauend ergänzt werden.

Der wesentliche Unterschied zur "do..while.."-Schleife ist, dass die Bedingung bei jener erst nach dem ersten Durcharbeiten des Schleifenblocks getestet wird, bei der "while.."-Schleife jedoch schon vor diesem ersten Durchlauf. Mithin gilt für die Anzahl n der Durchläufe des Anweisungsblocks bei einer "do..while.."-Schleife die Ungleichung "n >= 1", während bei der "while.."-Schleife gilt "n >= 0". Das mag als ein eher kleiner Unterschied erscheinen, kann aber beim Programmieren weitreichende und gelegentlich auch katastrophale Folgen haben.


Übungen:


  1. DIV, aber richtig!

    Schreiben Sie ein Programm zur Berechnung von a DIV b, das für alle (nicht zu großen) natürlichen Zahlen a und b das korrekte Ergebnis liefert. Sie können dazu das Projekt aus Aufgabe 2 klonen:
    In Delphi erstellen Sie dazu ein neues Verzeichnis und kopieren dorthinein die DPR-, die DFM- und die PAS-Datei des alten Projekts. Laden Sie dann die DPR-Datei aus dem neuen Verzeichnis, benennen Sie das Projekt um und speichern Sie alle Dateien nochmals ab. Im Kopf des Delphi-Editor-Fensters dürfen danach keine relativen Pfade mehr erscheinen!

    Entwickeln Sie das Projekt dann weiter. Dies können Sie auf zwei verschiedene Arten machen:
    1. Sie können bei der Repeat-Schleife bleiben und diese in eine IF-THEN-ELSE-Konstruktion einbetten.

    2. Sie können die Repeat- durch eine While-Schleife ersetzen. Beachten Sie, dass sie dabei auch die "Bedingung" umformulieren müssen! Trotzdem ist dies die elegantere Variante.
    In Java erstellen Sie dazu ein neues Verzeichnis und kopieren dorthinein die JAVA- und die JFM-Datei des alten Projekts. Laden Sie dann die JFM-Datei aus dem neuen Verzeichnis in den "JavaEditor", wobei dieser auch gleich die zugehörige JAVA-Datei lädt. Benennen Sie das Projekt um, indem Sie den Namen des Formulars ändern und danach alle Dateien (unter dem neuen Namen!) nochmals abspeichern.

    Entwickeln Sie das Projekt dann weiter. Dies können Sie auf zwei verschiedene Arten machen:
    1. Sie können bei der "do..while()"-Schleife bleiben und diese in eine "if()..else.."-Konstruktion einbetten.

    2. Sie können die "do..while()"- durch eine "while()"-Schleife ersetzen. Dies ist die elegantere Variante.
    Lösungsvorschlag: [Delphi] [Java]


  2. MOD ist die Krönung!

    Klonen Sie zunächst das Projekt von Aufgabe 3!

    Mit nur ganz wenigen Änderungen können Sie daraus ein Programm entwickeln, das den Rest berechnet, der bei der Ganzzahldivision übrig bleibt. Der Rest, den a bei Ganzzahldivision durch b läßt, wird mit "a MOD b" bezeichnet (lies "a modulo b").
    Schreiben Sie ein solches Programm!

    Wenn Sie DIV und MOD begriffen haben, können Sie nachträglich verstehen,
    wie Sie in der 4. Klasse der Grundschule Divisionen geschrieben haben:
    "17 : 3 = 5 R 2" enthält sowohl "17 DIV 3 = 5" als auch "17 MOD 3 = 2"

    Lösungsvorschlag: [Delphi] [Java]



Delphi kennt schon von Haus aus die Verknüpfungen "DIV" und "MOD": wir können sie in Termen genau so einsetzen wie "+", "-" oder "*". Voraussetzung ist, dass diese Ganzzahl-Operatoren nur auf INTEGER-Zahlen angewendet werden. Den Versuch, "3.2 MOD 8" berechnen zu wollen, quittiert schon der Delphi-Compiler mit einer Fehlermeldung. Die Syntax für diese beiden neuen Rechenarten ist:

Verknüpfung Delphi-Syntax
DIV a DIV b
MOD a MOD b
Java kennt schon von Haus aus die Verknüpfungen "DIV" und "MOD": wir können sie in Termen genau so einsetzen wie "+", "-" oder "*". Die Syntax für diese beiden neuen Rechenarten ist:

Verknüpfung Java-Syntax
DIV a / b
MOD a % b

Wenn Sie "a / b" berechnen lassen, hängt das Ergebnis vom Typ der beteiligten Variablen ab: ist wenigstens eine Fließkommazahl dabei, dann wird die "normale" Division ausgeführt; sind beide Zahlen von einem ganzzahligen Typ, dann wird "a DIV b" berechnet und das Ergebnis als ganze Zahl (also z.B. int) zurückgegeben.
Wenig sinnvoll hingegen ist, dass Java erlaubt, den Ganzzahl-Operator MOD auch auf Fließkommazahlen anzuwenden: schließlich hat die "normale Division" eigentlich keinen Rest! Wenn a und b hingegen beide ganzzahlig sind, dann liefert "a % b" den korrekten ganzzahligen Wert von "a MOD b".

  1. Primzahltest

    Damit lassen sich interessante mathematische Fragestellungen bearbeiten. Ob zum Beispiel eine ganze Zahl a durch eine andere ganze Zahl b teilbar ist (d.h.: ob b ein Teiler von a ist), kann man entscheiden, indem man r := a MOD b bildet: ist r = 0, dann ist a (ohne Rest!) durch b teilbar, andernfalls nicht.

    1. Schreiben Sie ein Programm, das eine einzugebende ganze Zahl n darauf testet, ob sie eine Primzahl ist oder nicht, indem es für alle natürlichen Zahlen k von 2 bis (n-1) testet, ob k ein Teiler von n ist. Das Programm soll einen Antworttext liefern.

    2. Wenn Sie das Programm nach dem in a) skizzierten Verfahren gebaut haben, dann macht es eine Menge eigentlich unnötiger Rechenarbeit. Im Lösungsvorschlag wird zumindest die Suche nach einem Teiler von n dann abgebrochen, wenn der erste Teiler gefunden wurde. Falls aber kein Teiler von n gefunden wird, werden alle Zahlen von 2 bis n-1 getestet. Aber: mehr als die Hälfte all dieser Tests sind überflüssig! Warum? Zur Beantwortung dieser Frage brauchen Sie etwas Mathematik und eine Portion GMV...

      Probieren Sie mal einige Fälle mit Papier und Bleistift durch. Optimieren Sie dann das Programm: schreiben Sie es so um, dass es möglichst wenig überflüssige Rechenschritte macht!

      Lösungsvorschlag: [Delphi] [Java]



Zum vorigen Kapitel Zum Inhaltsverzeichnis Zum nächsten Kapitel