Programmieren

Entwurf von Programmschleifen

 aufwärts

Wie entwirft man eine Programm­schleife? Im Folgenden wird eine systematische Methode hierzu angegeben. Diese beruht auf der Erstellung eines Iterations­schemas, aus dem Iterations­gleichungen abgeleitet werden. Diese wiederum lassen sich unmittelbar in eine Programm­schleife umsetzen.

Die Programm­schleifen sind hier in der Programmier­sprache Java angegeben; eine ent­sprechende Visual-Basic-Version und eine Python-Version stehen ebenfalls zur Verfügung.

In funktionalen Programmier­sprachen wie etwa Haskell treten endrekursive Funktionen an die Stelle von Iteration. Auch hier lassen sich mithilfe eines parallelen Iterations­schemas in systematischer Weise Iterations­gleichungen gewinnen, die unmittelbar in ent­sprechende endrekursive Funktions­definitionen umgesetzt werden können.

Iterative Berechnungen

Ein wichtiges Anwendungs­gebiet für Programm­schleifen ist die iterative Berechnung von Funktions­werten.

Beispiel:  Die Berechnung von an, von n!, von ex, von π, von Binomial­koeffizienten usw. lässt sich durch Iterations­verfahren durchführen.

So lässt sich etwa an berechnen, indem der Anfangswert 1 n-mal mit a multi­pliziert wird. Der Funktions­wert von ex ergibt sich als Grenzwert einer Reihe. Ebenso lässt sich π durch eine Folge oder Reihe approximieren.

Iterationsschema

Ein Iterations­schema ist eine Tabelle, die für jede Iteration die Werte der beteiligten Variablen enthält. Für jede Variable, die während der Iteration ihren Wert ändert, ist eine Tabellen­zeile vorgesehen.

Beispiel:  Ein mögliches Iterations­schema für die Berechnung von an ist das folgende:

i01234...n
p1aa·aa·a·aa·a·a·a...an

Die Variable i dient zum Zählen der Iterationen, die Variable p enthält das jeweilige Zwischen­ergebnis nach jeder Iteration. Für die Variable a ist keine Zeile im Iterations­schema vorgesehen, da sie ihren Wert im Verlauf der Berechnung nicht ändert. Das Ergebnis der Berechnung ist der Wert von p in der Spalte, in der i = n ist.

Iterationsgleichungen

Aus dem Iterations­schema werden Iterations­gleichungen abgeleitet. Für jede Variable des Iterations­schemas wird eine Iterations­gleichung aufgestellt. Diese gibt an, wie der Wert der Variablen in jeder Spalte des Schemas ab der zweiten Spalte zu berechnen ist. Die Werte in der ersten Spalte werden durch Initialisierung festgesetzt.

Beispiel:  Die Iterations­gleichungen für das obige Iterations­schema lauten

Hierbei bezeichnet v' den Wert der Variablen v in der vorherigen Spalte.

So ergibt sich der Wert von i in jeder Spalte als Wert von i in der vorherigen Spalte plus 1. Der Wert von p ergibt sich als Wert von p in der vorherigen Spalte mal a.

Die Iterations­gleichungen gelten in diesem Beispiel für alle Spalten des Iterations­schemas außer der ersten Spalte. Die Werte der ersten Spalte werden durch Initialisierung festgesetzt:

Regeln für die Aufstellung der Iterationsgleichungen

Die Iterations­gleichungen lassen sich unmittelbar in ein Programm umsetzen, wenn die folgenden Regeln eingehalten werden.

  1. Die Reihenfolge der Variablen im Iterations­schema bestimmt die Reihenfolge der Iterations­gleichungen
  2. Die Iterations­gleichung für eine Variable v darf auf der rechten Seite nur folgende Variablen enthalten:
    1. Variablen w, die im Iterations­schema in derselben Spalte oberhalb von v stehen,
    2. Variablen w', die im Iterations­schema in der vorherigen Spalte auf gleicher Höhe oder unterhalb von v stehen,
    3. sonstige Variablen und Konstanten.
  3. Alle Variablen v, die in der Form v' auftreten, müssen initialisiert werden.

Anschaulich gesehen dürfen für die Berechnung eines Wertes im Iterations­schema nur die darüber­liegenden Werte oder die direkt links daneben und darunter liegenden Werte des Iterations­schemas benutzt werden. So dürfen für die Berechnung des Wertes an Position X nur Werte aus den mit x gekenn­zeichneten Feldern verwendet werden (und natürlich Werte von sonstigen Variablen und Konstanten).

   x 
   x 
  xX 
  x  
  x  
Bild 1: Zulässige Variablen auf der rechten Seite einer Iterationsgleichung

Beispiel:  In den obigen Iterations­gleichungen

i = i' + 1

p = p' · a

kommt auf der rechten Seite der Gleichung für i nur die Variable i' vor, die im Iterations­schema nicht oberhalb von i steht, sowie die Konstante 1. Auf der rechten Seite der Gleichung für p kommt nur die Variable p' vor, die im Iterations­schema nicht oberhalb von p steht, sowie die sonstige Variable a.

Bemerkung:  Ein Iterations­schema lässt sich auch für die funktionale Pro­grammierung mit der Programmier­sprache Haskell verwenden. In der funktionalen Pro­grammierung muss das Iterations­schema ein paralleles Iterations­schema sein, im Gegensatz zum oben definierten sequentiellen Iterations­schema. Bei einem parallelen Iterations­schema werden für die Berechnung der Werte nur Werte aus der vorherigen Spalte verwendet – die rechten Seiten der Iterations­gleichungen enthalten also nur Variablen "mit Strich". Das obige Iterations­schema für die Berechnung von an ist ein paralleles Iterations­schema – und zugleich auch ein sequentielles Iterations­schema, diese Eigen­schaften schließen sich also nicht aus.

Umsetzung der Iterationsgleichungen in ein While-Programm

Die nach den obigen Regeln auf­gestellten Iterations­gleichungen lassen sich direkt in eine While-Schleife umsetzen. Vor die While-Schleife wird die Deklaration und Initialisierung der beteiligten Variablen gesetzt. Als Schleifen­bedingung wird eine Bedingung gewählt, die im Iterations­schema für alle Spalten vor der Spalte gilt, in der das Ergebnis der Berechnung erwartet wird.

Beispiel:  Das Beispiel zur Berechnung von an ergibt, unter Benutzung der ent­sprechenden Iterations­gleichungen und Initialisierungen, folgendes Programm­stück. Voraus­gesetzt ist, dass die Variablen a und n bereits deklariert sind und Werte enthalten. Das Ergebnis der Berechnung ist der Wert von p nach Beendigung der Schleife.

int i=0, p=1;
while (i<n)
{
    i=i+1;
    p=p*a;
}

 

Weitere Beispiele

Berechnung von ln(2) durch alternierende Reihe

Die alternierende harmonische Reihe konvergiert (allerdings sehr langsam) gegen den Grenzwert ln(2).

ln(2)  =  1 – 1/2 + 1/3 – 1/4 + 1/5 – 1/6 + ...

Für die Berechnung der Reihe wird folgendes Iterations­schema verwendet:

n012345...
s 1/11/21/31/41/5...
v-11-11-11...
p011-1/21-1/2+1/3...  

Die Variable n zählt die Iterationen, s enthält jeweils das nächste Reihenglied, v das zugehörige Vorzeichen und p die jeweils aufgelaufene Partialsumme.

Aus dem Iterations­schema lassen sich folgende Iterations­gleichungen gewinnen:

Auf den rechten Seiten der Iterations­gleichungen werden nur Variablen verwendet, die nach dem Schema von Bild 1 zulässig sind.

Die Iterations­gleichungen gelten ab der zweiten Spalte. Die Initialisierung für die erste Spalte ist

Die Iterations­gleichungen und Initialisierungen werden in folgendes While-Programm umgesetzt. Die Schleife wird 1000-mal durchlaufen. Das Ergebnis ist der Wert von p nach Ende der Iteration.

int n=0, v=-1;
double s, p=0;
while (n<1000)
{
    n=n+1;
    s=1.0/n;
    v=-v;
    p=p+v*s;
}
Berechnung der Fibonacci-Zahlen

In der Fibonacci-Folge ergibt sich jedes Folgen­element als Summe der beiden vorher­gehenden Elemente:

f  =  1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...

Für die Berechnung der Folge wird folgendes Iterations­schema verwendet:

i1234567...
h 112358...
g11235813...
f123581321...

Aus dem Iterations­schema lassen sich folgende Iterations­gleichungen gewinnen:

Die Iterations­gleichungen gelten ab der zweiten Spalte. Die Initialisierung für die erste Spalte ist

Die Iterations­gleichungen und Initialisierungen werden in folgendes While-Programm umgesetzt, das hier in eine Funktions­definition für die Berechnung der n-ten Fibonacci-Zahl eingesetzt ist (n = 0, 1, 2, 3, ...). Für die 0-te Fibonacci-Zahl ist keine gesonderte Behandlung erforderlich, da die Initialisierung f = 1 auch für n = 0 gültig ist.

long fib(int n)
{
    int i=1;
    long h, g=1, f=1;
    while (i<n)
    {
        i=i+1;
        h=g;
        g=f;
        f=g+h;
    }
    return f;
}

Aufgaben

Aufgabe 1:  (Berechnung der eulerschen Zahl e)

Die folgende Reihe konvergiert gegen die eulersche Zahl e = 2,71828...:

e    =     Summe n = 0, ..., unendlich  
1
n!
    =    
1
0!
  + 
1
1!
  + 
1
2!
  + 
1
3!
  + 
1
4!
  +  . . .

Stellen Sie ein Iterations­schema für die Berechnung von e auf. Leiten Sie daraus die zugehörigen Initialisierungen und Iterations­gleichungen ab und setzen Sie diese in eine While-Schleife um. Brechen Sie die While-Schleife ab, wenn der neu hinzu­gekommene Summand kleiner als 10-14 ist.

Erstellen Sie unter Benutzung dieser While-Schleife eine Funktion double e() zur Berechnung von e.

Aufgabe 2:  (Berechnung von π)

Die Leibniz-Reihe konvergiert (allerdings sehr langsam) gegen den Grenzwert π/4:

π/4  =  1 – 1/3 + 1/5 – 1/7 + 1/9 – 1/11 + 1/13 – ...

Stellen Sie ein Iterations­schema für die Berechnung von π/4 auf. Leiten Sie daraus die zugehörigen Initialisierungen und Iterations­gleichungen ab und setzen Sie diese in eine While-Schleife um. Brechen Sie die While-Schleife ab, wenn der neu hinzu­gekommene Summand betragsmäßig kleiner als 10-4 ist.

Erstellen Sie unter Benutzung dieser While-Schleife eine Funktion double pi() zur (grob angenäherten) Berechnung von π.

Aufgabe 3:  (Berechnung von Binomial­koeffizienten)

Der Binomial­koeffizient n über k ist definiert als

Binomialkoeffizient Klammer auf nBinomialkoeffizient Klammer zu
 k
    =    
n!
k! · (n-k)!

Da der Bruch durch (n-k)! gekürzt werden kann, gilt

Binomialkoeffizient Klammer auf nBinomialkoeffizient Klammer zu
 k
    =    
(n-k+1) · ... · n
1 · ... · k

Als Beispiel ist etwa

Binomialkoeffizient Klammer auf49Binomialkoeffizient Klammer zu
6
    =    
44 · 45 · 46 · 47 · 48 · 49
1· 2 · 3 · 4 · 5 · 6
    =    13983816

 

Stellen Sie ein Iterations­schema für die Berechnung von n über k auf. Leiten Sie daraus die zugehörigen Initialisierungen und Iterations­gleichungen ab und setzen Sie diese in eine While-Schleife um, innerhalb einer Funktion long binom(long n, long k).

 

Weitere Aufgaben ...

 

 

Weiter mit:   [Funktionen]   oder   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©  
Valid HTML 4.01 Transitional

Hochschule Flensburg
Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik