Immer diese Wiederholungen: Schleifen

Willemers Informatik-Ecke

Diese Seite basiert auf Inhalten aus meinem Buch "Einstieg in C++" und dessen Nachfolger C++. Der Einstieg

Die Inhalte dieser Website unterliegen meinem Urheberrecht und dürfen trotz inhaltlicher Überschneidungen mit dem Buch C++. Der Einstieg dank der freundlichen Genehmigung des Verlags Wiley-VCH hier erscheinen.

Es gibt viele Aufgaben, in denen Befehle wiederholt werden sollen, bis ein bestimmtes Ergebnis erzielt worden ist. Eine solche Wiederholung nennt man in Programmen eine Schleife. Jede Form des Zählens wird im Programm in einer Schleife realisiert. Bei der Nullstellenberechnung nach Regula Falsi werden immer neue Annäherungen in einer Schleife berechnet, bis die Nullstelle der Funktion in der vorgegebenen Genauigkeit gefunden wurde. In Computerspielen dürfen Sie so lange ballern, bis Ihr letztes Raumschiff abgeschossen wurde. Eine Schleife hat den Wiederholungscharakter, enthält aber auch immer eine Bedingung, unter der die Schleife verlassen wird, oder positiv formuliert: Die Schleife wird so lange durchlaufen, wie die Schleifenbedingung gilt.

Endlosschleife

Achten Sie besonders auf die Formulierung der Schleifenbedingung. Nicht nur Anfängern passiert es, dass die Schleife niemals endet, weil die Schleifenbedingung niemals unwahr wird. Eine solche Schleife wird Endlosschleife genannt. Eine andere Ursache für eine Endlosschleife kann darin bestehen, dass die Bedingung zwar richtig formuliert ist, aber dass der Programmierer vergisst, die Daten, die in der Bedingung abgefragt werden, innerhalb der Schleife zu ändern.

Kopfgesteuert: while

Solange

Die einfachste Schleife wird durch das Schlüsselwort while eingeleitet. Die deutsche Übersetzung lautet >>solange<<. Und damit lässt sich bereits gut beschreiben, wie eine solche Schleife arbeitet. Sie wiederholt Vorgänge, solange eine bestimmte Bedingung erfüllt ist. Auch im Alltag verwenden wir solche Schleifen. Solange die Suppe noch nicht salzig genug ist, schüttet man noch einen Teelöffel Salz hinein. Und wie in diesem Beispiel zuerst der Salzgehalt geprüft wird, so prüft auch die while-Schleife zuerst die Bedingung und führt dann erst die Anweisung aus.

Analogie zu if

Der Syntax ähnelt sehr einer if-Anweisung. Und tatsächlich bestehen die Unterschiede nur darin, dass die Schleife die Anweisung wiederholt. Ist die Bedingung von vornherein nicht erfüllt, verhält sich die Schleife exakt wie die if-Anweisung: Sie führt die Anweisung nicht aus.

Die Schleife beginnt mit dem Schlüsselwort while. In Klammern folgt die Bedingung, unter der die direkt anschließende Anweisung ausgeführt wird. Auch hier können mehrere Anweisungen zu einem Anweisungsblock zusammengefasst werden, wenn sie in geschweiften Klammern stehen. Abbildung {grafwhile} zeigt den Syntaxgraph.

Grafik nur im Buch vorhanden

Zählen für Anfänger

Als erstes Beispiel bringen wir dem Computer das Zählen bei. Denken Sie darüber nach, was Sie tun, wenn Sie zählen. Zunächst beginnen Sie bei einer bestimmten Zahl, typischerweise bei eins. Dann folgt die Wiederholung, in der Sie immer den bisherigen Wert um eins erhöhen. Da Sie auch irgendwann einmal etwas anderes tun wollen als zählen, werden Sie bei einem bestimmten Wert die Wiederholung abbrechen.

Zählen für Computer

Im Programm verwenden Sie eine Variable, die Sie mit dem Startwert vorbesetzen. Dieser Startwert muss vor der Schleife gesetzt werden, sonst würde die Variable in jeder Runde auf ihren Ausgangspunkt zurück gesetzt, und die Schleife würde ewig rotieren. Danach soll das Programm in die Schleife eintreten, in der die Variable immer um eins erhöht wird. Die Schleife beginnt mit dem Schlüsselwort while. Direkt dahinter wird in Klammern die Bedingung formuliert. Solange diese Bedingung gilt, bleibt das Programm innerhalb der Schleife. Wenn Sie bis zehn zählen wollen, müssen Sie hier prüfen, ob die Variable kleiner oder gleich 10 ist. Direkt anschließend an die Bedingung können Sie eine Anweisung angeben, die in der Schleife wiederholt werden soll. Da Sie ja einerseits die Variable um eins erhöhen wollen und andererseits den aktuellen Stand auf dem Bildschirm ausgeben wollen, brauchen Sie aber zwei Anweisungen, die in der Schleife ausgeführt werden sollen. Das kann aber leicht mit einem Block, also geschweiften Klammern gelöst werden. In den Block wird also die Ausgabe der Variablen und die anschließende Erhöhung der Variablen gesetzt.
#include <iostream>
using namespace std;
int main()
{
    i = 1;
    while (i <= 10) // Schleifenbedingung
    {
        cout << i << endl;  // Aktion
        i++; // Ohne diese Erhöhung wird es eine Endlosschleife
    }
}

Grenzfragen

Leicht entstehen Fehler bei der Festlegung der Schleifengrenzen. Würden Sie statt <= nur das Kleinerzeichen verwenden, würde das Programm nur bis neun zählen. Der Grund ist, dass sobald der Inhalt von i den Wert 10 erreicht, die Bedingung nicht mehr gilt und damit das Schleifeninnere nicht mehr betreten wird. Sie können auch eine Schleife bilden, die zehnmal durchläuft, indem Sie bei 0 beginnen und abfragen, ob die Variable kleiner als zehn ist. Dann würde die Variable i von 0 bis 9 laufen. Wenn Sie i allerdings vor der Ausgabe erhöhen, erhalten Sie wieder die Zahlen von 1 bis 10.
#include <iostream>
using namespace std;
int main()
{
    int i = 0;
    while (i < 10)
    {
        i++;
        cout << i << endl;
    }
}

Test am Kopf

Die while-Schleife prüft die Bedingung am Schleifenkopf. Das bedeutet, dass die Anweisungen in der Schleife gar nicht ausgeführt werden, wenn die Bedingung vor dem Betreten der Schleife unwahr ist.

Struktogramm

Das Struktogramm der while-Schleife sehen Sie in Abbildung {whilediagramm}. Die Abfrage, ob die Schleife weiter durchlaufen wird, findet sich zu Anfang und >>umfasst<< die Anweisung oder den Anweisungsblock, der innerhalb der Schleife ausgeführt wird.

Grafik Struktogramm der while-Schleife nur im Buch vorhanden

Als weiteres Beispiel wird noch einmal gezählt, diesmal aber rückwärts.

int i = 10;
while (i > 0)
{
    i--;
}
Hier wird die Zählvariable i mit 10 vorbesetzt. In der Schleifenbedingung wird geprüft, ob i größer als 0 ist. Das ist wahr, also wird die Schleife betreten und der Schleifenkörper ausgeführt. Darin wird lediglich die Variable i um 1 vermindert, so dass i nach dem ersten Durchlauf immer noch 9 enthält. Das ist immer noch größer als 0. Die Schleife wird so oft durchlaufen, bis i durch das Dekrementieren 0 wird. Bei der nächsten Prüfung am Schleifenkopf ist die Bedingung nicht mehr gültig, und die Schleife wird sofort verlassen. Im Listing fehlt die Ausgabe. Als kleine Übung können Sie darüber nachdenken, was wohl ausgegeben wird, wenn Sie die Ausgabeanweisung vor oder nach dem Dekrementieren von i in die Schleife setzen. Wenn Sie sicher sind, was passieren wird, probieren Sie es aus!

Fußgesteuert: do...while

In manchen Situationen ist die Prüfung am Kopf der Schleife ungünstig. Manchmal wollen Sie eine Aktion durchführen und werden erst an ihrem Ende erkennen können, ob die Aktion wiederholt werden soll. Ein Kind wird beispielsweise seinen Opa so lange um Süßigkeiten anbetteln, bis dieser keine mehr hat. (Erfahrene Eltern werden zu Recht einwerfen, dass die Abschlussbedingung von dem System Opa nicht eingehalten wird.) Das Kind wird in jedem Fall erst einmal betteln, ansonsten kann es die Bedingung gar nicht erst prüfen. In diesem Fall findet also die Prüfung erst nach dem Durchlauf des Schleifenkörpers statt.

Eingabeprüfung

In Programmen wird eine fußgesteuerte Schleife besonders bei Eingabeprüfungen eine typische Anwendung. Innerhalb der Schleife fordert das Programm vom Anwender eine Eingabe an. Erst dann wird geprüft, ob die Eingabe korrekt ist. Ist die Eingabe nicht zufriedenstellend, wird die Schleife wiederholt. Ein weiteres Beispiel ist das Spiel Minesweeper. Der Benutzer soll auf ein Feld klicken. Solange unter dem Feld keine Mine liegt, darf er weiterspielen. Sie können erst am Ende der Schleife feststellen, wohin der Benutzer geklickt hat. Der Syntaxgraph der do-while-Schleife ist in Abbildung {grafdowhile} zu sehen.

Grafik Syntaxgraph do-while nur im Buch vorhanden

Auch hier werden Sie in den meisten Fällen einen Block aus geschweiften Klammern verwenden, da eine Schleife meist mehrere Anweisungen umfasst.

Das Struktogramm unterscheidet sich von dem der while-Schleife darin, dass die Bedingung nun am Ende steht.

Grafik Struktogramm der do-while-Schleife nur im Buch vorhanden

Im folgenden Beispiel wird rückwärts gezählt. Betrachten Sie das Listing, und überlegen Sie, ob die Zahlen 10, 1 und 0 ausgegeben werden! Prüfen Sie, ob Ihre Vermutungen stimmen!

#include <iostream>
using namespace std;

int main()
{
    int i = 10;
    do
    {
        cout << i << endl;
        i--;
    }
    while(i>0);
}

Abgezählt: for

Die beiden bisher gezeigten Schleifen benötigten drei Elemente: Fehlt eines dieser Elemente oder ist es nicht korrekt, dann ist das Risiko einer Endlosschleife groß. Die for-Schleife enthält alle drei Elemente in ihrem Kopf. So sind sie an einer Stelle zusammengefasst und können leichter unter Kontrolle gehalten werden.

Eine sehr typische Anwendung für Schleifen ist das Zählen; und gerade hier zeigt sich besonders die Übersichtlichkeit der for-Schleife. Das folgende Beispiel zählt von 0 bis 9.

for (i=0; i<10; i++)
{
    cout << i << endl;
}

Zusammengefasst

In der Klammer, die dem Schlüsselwort for folgt, findet sich als Erstes eine Startanweisung, die die Variable i auf 0 setzt. Bei den while-Schleifen wurde diese Initialisierung vor der Schleife durchgeführt. Als Zweites ist die Schleifenbedingung zu erkennen. Die dritte Anweisung ist das Inkrementieren der Zählervariablen, die üblicherweise am Ende der Schleife steht. Diese drei Elemente werden je durch ein Semikolon getrennt. Die for-Schleife hat folgendes Aussehen:

Die Grafik Syntaxgraph für for ist nur im Buch vorhanden.

Die for-Schleife ist der while-Schleife sehr ähnlich. Sie verpackt ihre Fähigkeiten nur eleganter und bewirkt, dass der Programmierer nicht so leicht wichtige Elemente vergisst. Sie könnten das obige Schema leicht auch als while-Schleife darstellen.

Startanweisung;
while ( Bedingung)
{
    Schleifenkörper;
    Schlussanweisung;
}

Entsprechend unterscheidet sich das Struktogramm nicht von dem der while-Schleife. Es wird lediglich inhaltlich der Kopf der Schleife in den Abfragebereich geschrieben.

Die Grafik Struktogramm der for-Schleife ist nur im Buch vorhanden.

Manche Programmierer setzen beim Struktogramm die Schlussanweisung in das Feld des for-Befehls zu Startanweisung und Bedingung.

Mehrfachanweisungen

Wenn Sie mehrere Anweisungen in der Start- oder Schlussanweisung benötigen, können Sie nicht einfach einen Block mit geschweiften Klammern in die runde Klammer setzen. Allerdings ist es möglich, mehrere Anweisungen in die Start- oder Schlussanweisung zu stellen, indem man sie durch ein Komma trennt. Das folgende Beispiel illustriert dies:
#include <iostream>
using namespace std;

int main()
{
    int i, a;
    for (i=0, a=10; i<5; i++, a--)
    {
       cout << i << "-" << a << endl;
    }
}

Komma

Der Hintergrund ist, dass das Komma ein Ausdrucksoperator ist, der zwei Ausdrücke voneinander trennt. Dabei wird der letzte Ausdruck ausgewertet. Entsprechend ist aus Sicht des Compilers i=0, a=10 eine Anweisung, die aus zwei Ausdrücken besteht, die wiederum durch einen Komma-Operator getrennt sind.

Anweisungen weglassen

Die drei Elemente in der Klammer der for-Schleife müssen nicht besetzt werden. Wenn Sie keine Startanweisung benötigen, lassen Sie sie einfach weg und setzen nur ein Semikolon. Auch die Schlussanweisung kann weggelassen werden. Dann folgt nach dem zweiten Semikolon gleich die schließende Klammer.

Endlosschleife

Eine besondere Variante der for-Schleife werden Sie vielleicht hin und wieder in Programmbeispielen sehen. Will ein Programmierer bewusst eine Endlosschleife programmieren, so verwendet er oft die for-Schleife und schreibt in die Klammer nichts außer den beiden Semikola. Die leere Bedingung wird von C++ als wahr empfunden. C++ ist also offensichtlich grundlegend optimistisch eingestellt. Da die Schleifenbedingung nie unwahr wird, wird solch eine Schleife nie verlassen. Solche Endlosschleifen haben im Allgemeinen einen anderen Ausstieg als den über die Kopfbedingung. Dazu gehört beispielsweise der Befehl break, der im nächsten Abschnitt beschrieben wird.
for (;;) // läuft bis zum nächsten Stromausfall
{
    ...
}

Schleifensprünge: break und continue

Normalerweise sollte allein die Schleifenbedingung bestimmen, wann eine Schleife verlassen wird. Dadurch hat die Schleife einen klar definierten Ausstieg. Einen Sonderfall ermöglicht der Aufruf von break. Er bewirkt ein sofortiges Verlassen der Schleife. Typischerweise wird er in der Mitte eines Schleifenkörpers eingesetzt, wenn eine besondere Situation, beispielsweise ein Fehler, eintritt.
fehler=0;
while (a>0)
{
    ...
    c=4;
    if (fehler==9)
    {
        break;
    }
    a++;
    ...
}

Kein guter Stil

Dieser Mechanismus ist natürlich ungeheuer praktisch. Sie können sofort auf Ereignisse reagieren, die das Verlassen der Schleife erfordern. Allerdings hat diese Konstruktion zwei Schönheitsfehler: Erstens ist an der Schleifenbedingung hinter dem while nicht mehr allein erkennbar, unter welchen Bedingungen die Schleife beendet wird, und zweitens stehen die Anweisungen vor und hinter der if-Abfrage scheinbar auf der gleichen Ebene. Dennoch wird die Anweisung a++ nicht unter den gleichen Bedingungen ausgeführt wie c=4.

Eine allzu häufige Verwendung von break zeugt von mangelnder Planung. Anstatt sorgfältig eine Bedingung zu formulieren und durch eine if-Abfrage den Ablauf zu steuern, wird die Schleife spontan abgebrochen. Der folgende Ablauf ist äquivalent zu dem vorigen, hat aber den Vorteil, dass der Ablauf und das Ende der Schleife deutlicher werden.

fehler=0;
while (fehler!=9 && a>0)
{
    ...
    c=4;
    if (fehler!=9)
    {
        a++;
        ...
    }
}
Bevor Sie break verwenden, um eine Schleife zu verlassen, sollten Sie darüber nachdenken, ob Sie den Ablauf nicht eleganter gestalten können. Wenn Sie dennoch gute Gründe haben, mit break zu arbeiten, sollten Sie wenigstens am Schleifenkopf durch einen Kommentar auf diese Abnormität hinweisen.

continue

In eine ähnliche Kategorie fällt der Befehl continue. Dieser verlässt die Schleife allerdings nicht, sondern springt sofort an das Schleifenende. Der dem Befehl continue folgende Teil des Schleifenkörpers wird also nicht bearbeitet.
while (a>0)
{
    ...
    c=4;
    if (fehler==9)
    {
        continue;
    }
    a++;
    ...
}
Die Verwendung von continue lässt sich noch leichter umgehen als die von break. Der einzige Vorteil, den continue gegenüber der Verwendung einer if-Abfrage hat, ist die Verringerung der Einrückungstiefe für die Anweisung a++. Aber genau das ist gleichzeitig der Nachteil: Man kann nicht an der Einrückung ablesen, dass diese Befehle nur dann ausgeführt werden, wenn die Variable fehler nicht den Wert 9 enthält.
while (a>0)
{
    ...
    c=4;
    if (fehler!=9)
    {
        a++;
        ...
    }
}
Die einzig wirklich sinnvolle Anwendung des break-Befehls findet sich in der switch-Anweisung. Hier liegt es in der Natur der Sache, dass nach dem Abarbeiten eines Falles die Anweisung per Sprung verlassen wird.

Der brutale Sprung: goto

Label

Die Anweisung goto kann an eine beliebige Stelle innerhalb der gleichen
Funktion springen. Als Sprungziel wird ein so genanntes Label gesetzt. Ein Label besteht aus einem Namen und einem Doppelpunkt. Hinter jedem Label muss mindestens eine Anweisung stehen.
if (a==0)
{
    a++;
    goto Dazwischen;
}
b+=2;
if (b>6)
{
    goto GanzHinten;
    Dazwischen:
    // hier ist b>6 oder a==1
    b=4;
}
else
{
    c=2;
}
GanzHinten:
a++;
Der Sprung an die Stelle Dazwischen: zeigt, welcher Unfug mit der goto-Anweisung möglich ist. Obwohl dieser Sprung vom Compiler nicht bemängelt wird, fällt es schwer vorherzusagen, was passiert. Wenn Sie schon einen goto-Befehl verwenden, dann sollten Sie ihn höchstens zum Verlassen von verschachtelten Schleifen einsetzen und nicht in andere Blöcke hineinspringen.

Mittelalter

Wenn Sie häufiger goto in Ihren Programmen verwenden, werden Sie den gleichen Blick in den Gesichtern Ihrer Kollegen feststellen, den Sie hervorrufen, wenn Sie in der Kantine Ihr Schnitzel mit einer Streitaxt teilen.

In alten (wirklich alten) Programmiersprachen gab es nur den absoluten Sprung, um eine andere Stelle im Programm zu erreichen. Da diese Programme sehr unübersichtlich wurden, gab es in den 70er Jahren einen Kreuzzug gegen die Verwendung des goto. Moderne Sprachen haben durch Abfragen und Schleifen alles an Bord, um auf den Befehl goto verzichten zu können. Ein Sprung erschwert die Nachvollziehbarkeit des Programmablaufs. Darum sollten Sie ihn vermeiden.

Beispiele

Schleifen und Abfragen sind ein Grundbestandteil jedes Programms. Sie brauchen einige Übung, um in den Aufgabenstellungen Abfragen und Schleifen zu erkennen und zu lernen, wie sie kombiniert werden. Zu diesem Zweck werden in diesem Abschnitt einige Beispiele betrachtet. Die Beispiele sind so gewählt, dass sie zeigen, wie Schleifen und Abfragen ineinander verschachtelt werden. Die Nassi-Schneidermann-Diagramme werden zur Veranschaulichung, aber auch als Design-Werkzeuge eingesetzt.

Primzahlen

Primzahlen sind Zahlen, die nur durch sich selbst und 1 teilbar sind. Für die Berechnung der Primzahlen gibt es keine Formel, sondern man muss für jede kleinere Zahl prüfen, ob sie sich ohne Rest dividieren lässt.

Äußere Schleife

Das Programm soll alle Primzahlen zwischen 3 und 100 ausgeben. Es gibt also eine große Zählschleife für alle Kandidaten.
#include <iostream>
using namespace std;

int main()
{
    const int MaxPrimzahl=100; // Ende der Berechnung
    int Primzahl;   // Testkandidat
    for (Primzahl=3; Primzahl<=MaxPrimzahl; Primzahl++)
    // Durchlaufe alle Kandidaten
    {
        // Pruefe, ob Primzahl wirklich eine Primzahl ist
        // Testausgabe:
        cout << Primzahl << " ";
    }
    cout << endl;
}
In die Schleife wurde erst einmal eine Testausgabe gesetzt. Damit können Sie sehen, dass die Primzahlenkandidaten tatsächlich von 3 bis 100 laufen. Wenn Sie unsicher sind, ob Programmteile das tun, was Sie von Ihnen erwarten, sollten Sie solche Testhilfen ruhig in Ihr Programm einbauen. Sie können Sie ja später wieder löschen. Sollte Ihnen die Menge der Ausgaben zu groß werden, reduzieren Sie einfach MaxPrimzahl für die Testphase auf 10!

Innere Schleife

Im nächsten Schritt soll in der Schleife jeder Kandidat geprüft werden. Dazu wird er durch alle Zahlen zwischen 2 und seinem eigenen Wert minus eins dividiert. Wenn bei dieser Division kein Rest bleibt, sind die Zahlen durcheinander teilbar und der Kandidat ist keine Primzahl. Sie brauchen also eine weitere Schleife innerhalb der Schleife. In dieser Schleife wird der Divisor hochgezählt. Er startet bei 2 und läuft bis Primzahl-1.
#include <iostream>
using namespace std;

int main()
{
    const int MaxPrimzahl=100;
    int Primzahl, Divisor;
    for (Primzahl=3; Primzahl<=MaxPrimzahl; Primzahl++)
    {
        // Pruefe, ob Primzahl wirklich eine Primzahl ist
        for (Divisor=2; Divisor<=Primzahl-1; Divisor++)
        {
            // Testausgabe
            cout << Divisor << " ";
        }
        cout << endl;
    }
    cout << endl;
}

Primzahltest

Nun muss geprüft werden, ob Primzahl durch Divisor teilbar ist. Dazu kennen Sie bereits den Befehl % für die Modulo-Rechnung. Sie liefert 0, wenn beim Teilen kein Rest bleibt. Wir müssen also eine Abfrage konstruieren, die prüft, ob beim Teilen von Primzahl durch Divisor kein Rest bleibt.
#include <iostream>
using namespace std;

int main()
{
    const int MaxPrimzahl=100;
    int Primzahl, Divisor;
    for (Primzahl=3; Primzahl<=MaxPrimzahl; Primzahl++)
    {
        // Pruefe, ob Primzahl wirklich eine Primzahl ist
        for (Divisor=2; Divisor<Primzahl; Divisor++)
        {
            // Ist das restlos teilbar?
            if (0==Primzahl % Divisor)
            {
                // Zahl ist teilbar, ist also keine Primzahl!
                // Testausgabe:
                cout << Primzahl << "-" << Divisor << endl;
            }
        }
        cout << endl;
    }
    cout << endl;
}
Sie sind der Lösung schon recht nahe. Wenn Sie das Programm laufen lassen, können Sie sehen, wie die Primzahlkandidaten mit ihren Teilern angezeigt werden. Es werden also die Zahlen angezeigt, die keine Primzahlen sind, denn Primzahlen haben keine Teiler. Wenn sich das Programm nun merkt, dass es an diese Stelle gekommen ist, weiß es, dass dieser Kandidat keine Primzahl ist. Um sich Zustände zu merken, verwenden Sie am besten eine boolesche Variable.
#include <iostream>
using namespace std;

int main()
{
    const int MaxPrimzahl=100;
    int Primzahl, Divisor;
    bool istEinePrimzahl;
    cout << "2";
    for (Primzahl=3; Primzahl<=MaxPrimzahl; Primzahl++)
    {
        istEinePrimzahl = true;
        // Pruefe, ob Primzahl wirklich eine Primzahl ist
        for (Divisor=2; Divisor<Primzahl; Divisor++)
        {
            // Ist das restlos teilbar?
            if (0==Primzahl % Divisor)
            {
                // Zahl ist teilbar, ist also keine Primzahl!
                istEinePrimzahl = false;
            }
        }
        // Pruefung ist beendet.
        // Wenn es eine Primzahl ist, ausgeben!
        if (istEinePrimzahl)
        {
            cout << ", " << Primzahl;
        }
    }
    cout << endl;
}

Status merken

Dieses Programm erfüllt die Anforderungen, die wir gestellt hatten. Zu Anfang wird eine boolesche Variable namens istEinePrimzahl definiert. Für jeden neuen Kandidaten wird diese Variable auf true gesetzt. Sobald ein Teiler gefunden wird, wird sie auf false gesetzt. Nachdem alle Divisoren durchgetestet worden sind, wird der Kandidat ausgegeben, sofern istEinePrimzahl immer noch true ist.

Die Zahl 2 wird der Vollständigkeit halber einfach zu Anfang direkt ohne explizite Berechnung ausgegeben.

Optimierung

Allerdings ist diese Lösung nicht optimal. So wird die innere Schleife auch dann noch bis zum Ende durchlaufen, wenn der Kandidat bereits durch 2 teilbar ist. Das können Sie leicht abstellen, indem die Schleife eine zusätzliche Bedingung erhält. Es wird wie bisher geprüft, ob alle Divisoren für den Kandidaten durchlaufen wurden, und ergänzend, ob bisher noch keine Teilbarkeit festgestellt wurde.
#include <iostream>
using namespace std;

int main()
{
    const int MaxPrimzahl=100;
    int Primzahl, Divisor;
    bool istEinePrimzahl;
    cout << "2";
    for (Primzahl=3; Primzahl<=MaxPrimzahl; Primzahl++)
    {
        istEinePrimzahl = true;
        // Pruefe, ob Primzahl wirklich eine Primzahl ist
        for (Divisor=2; istEinePrimzahl && Divisor<Primzahl;
             Divisor++)
        {
            // Ist das restlos teilbar?
            if (0==Primzahl % Divisor)
            {
                // Zahl ist teilbar, ist also keine Primzahl!
                istEinePrimzahl = false;
            }
        }
        // Pruefung ist beendet.
        // Wenn es eine Primzahl ist, ausgeben!
        if (istEinePrimzahl)
        {
            cout << ", " << Primzahl;
        }
    }
    cout << endl;
}
Dieses Programm liefert dieselben Ergebnisse, läuft aber wesentlich effizienter. Vielleicht bemerken Sie das erst, wenn Sie MaxPrimzahl auf 10.000 setzen. Zum Abschluss sehen Sie in Abbildung {primzahldiagramm} das Struktogramm des Primzahlprogramms.

Grafik ist nur im Buch vorhanden

Größter gemeinsamer Teiler

Der größte gemeinsame Teiler (ggT) zweier Zahlen ist die größte der Zahlen, durch die beide Zahlen restlos teilbar sind. Die Berechnung des größten gemeinsamen Teilers wird vor allem zum Kürzen von Brüchen eingesetzt. Werden Zähler und Nenner jeweils durch den größten gemeinsamen Teiler dividiert, ist der Bruch optimal gekürzt. Der Algorithmus zur Berechnung des größten gemeinsamen Teilers könnte auf einer Primzahlenberechnung basieren. Dazu würde man beide Zahlen in ihre Primfaktoren zerlegen und alle gemeinsamen Primfaktoren multiplizieren. Aber es geht noch einfacher. Euklid hat bereits vor über 2000 Jahren ein sehr leicht umzusetzendes Verfahren beschrieben, wie der ggT zu berechnen ist.

Euklid

Die beiden Zahlen, deren ggT zu suchen ist, nennen wir a und b. Die Idee beruht auf der Erkenntnis, dass der ggT nicht nur Teiler von a und b ist, sondern auch von b und (a-b), sofern b größer als a ist. (Ich nehme mal an, dass Sie nicht an einem Beweis dieser Erkenntnis interessiert sind.) Man kann also, statt a und b zu untersuchen, auch b und (a-b) untersuchen. Damit braucht die größere der beiden Zahlen schon nicht mehr untersucht zu werden. Mit den beiden neuen Zahlen kann man aber wieder genauso verfahren wie mit a und b. Wieder wird statt der größeren Zahl die Differenz der beiden Zahlen weiterverwendet. Wenn man dieses Verfahren so lange wiederholt, bis die kleinere Zahl 0 wird, muss die andere Zahl der ggT sein.

Zuerst das Struktogramm

In diesem Beispiel soll die Entwicklung des Programms mit dem Struktogramm beginnen. Zunächst werden die beiden Kandidaten eingelesen. Danach läuft eine Schleife so lange, wie der kleinere Wert größer als 0 ist. Innerhalb der Schleife muss geprüft werden, welche die größere der beiden Zahlen ist. Gegebenenfalls werden die Werte noch getauscht, bevor sie voneinander abgezogen werden.

Grafik nur im Buch vorhanden

Tauschen

Damit ist die allgemeine Beschreibung des Algorithmus formalisiert und in ein Struktogramm gefügt. Fast alles lässt sich leicht direkt in C++-Code umsetzen. Lediglich das Tauschen des Variableninhalts muss näher beschrieben werden, bevor es in Programmcode umgesetzt werden kann. Der spontane Gedanke wäre, erst a=b und dann b=a zu schreiben. Das wird aber nicht funktionieren, weil der Variableninhalt von a in der ersten Zuweisung überschrieben wird und damit verloren geht. Es muss also eine Hilfsvariable verwendet werden, in die zuerst der Inhalt von a gesichert wird, bevor er überschrieben wird.
hilf = a;
a = b;
b = hilf;
Das Tauschen wird jetzt noch in das Struktogramm eingefügt. Gleichzeitig werden die Bezeichnungen der Syntax von C++ angenähert.

Grafik nur im Buch vorhanden

Übertragen in C++

Nun ist es eine leichte Übung, dieses Struktogramm in ein entsprechendes C++-Programm zu überführen. Das Struktogramm kann also eine Hilfe sein, ein Programm zu entwickeln, vor allem, wenn komplexere Abläufe vorliegen.
#include <iostream>
using namespace std;
int main()
{
    int a, b, hilf;
    cin >> a;
    cin >> b;
    while (b>0)
    {
        if (b>a)
        {
            // Tausche a und b
            hilf = a;
            a = b;
            b = hilf;
        }
        a = a - b;
    }
    cout << a << endl;
}

Übungen


Informatik-Ecke Einstieg in C++ (C) Copyright 2005 Arnold Willemer