Nach einem alten Paradoxon von Zenon:
Achilles und die Schildkröte laufen um die Wette. Da Achilles schneller ist als die Schildkröte, bekommt die Schildkröte einen Vorsprung.

Man kann behaupten, dass Achilles die Schildkröte niemals einholen kann, denn immer wenn Achilles dort ankommt, wo er die Schildkröte gesehen hat, dann ist sie schon zu einer neuen Position weitergelaufen. Dieser Vorgang wiederholt sich unendlich oft.

Mathematisch gesprochen: man muss unendlich oft über eine Wegstrecke summieren; kann diese Summe einen endlichen Wert annehmen?
Angenommen, die Schildkröte läuft halb so schnell wie Achilles und der Vorsprung beträgt am Anfang eine Längeneinheit. Dann lässt sich der Prozess so darstellen:
Schrittnummer | Weg Achilles | Weg Schildkröte | Differenz |
Schritt 1: | 1 LE | 0,5 LE | 0,5 LE |
Schritt 2: | 0,5 LE | 0,25 LE | 0,25 LE |
Hierbei gibt sich für den Weg von Achilles folgende Summe:
sAchilles = 1 + 1/2 + 1/4 + 1/8 + 1/16 + ...

Dieser Summe kann man leicht ansehen, dass sie sich an die Zahl 2 annähert, denn ab dem zweiten Summenglied kommt immer die Hälfte zwischen der erreichten Position und 2 hinzu. Achilles hat die Schildkröte also bei 2 LE eingeholt, obwohl unendlich viele Weg- und Zeitintervalle addiert wurden.
Unendliche Summen, deren n-tes Glied sich nach einer Formel xn = f(n) berechnen lässt, heißen Reihen.
Beispiele:
- Berechnung von π :
Eine mögliche Berechnung von π geht über die Leibniz-Reihe:
π/4 = 1 - 1/3 + 1/5 - 1/7 + 1/9 - ...
mit f(n) = (-1)n · 1/(2n+1) Beginn bei n = 0
- Berechnung von sin x :
Um die Funktion sin x im Computer zu simulieren werden die Werte entweder aus einer
Tabelle gelesen, oder nach der folgenden Reihenformel berechnet:
sin x = x - x3/3! + x5/5! - x7/7! + ...
Das sukzessive Annähern an einen festen Wert nennt man auch Iteration. Dabei berechnet sich der neue (besser angenäherte) Wert aus dem alten Wert:
x n+1 = f(xn)
Beispiele:
- Berechnung der Wurzel einer Zahl nach dem Heron-Verfahren:
Gesucht ist diejenige Zahl, deren Quadrat a ergibt.
Als Startwert für x nimmt man z. B. die 1. Die nächste "Näherung" findet man,
indem man die Zahl sucht, mit der man x multiplizieren muss um a zu erhalten.
Diese Zahl erhält man, indem man a durch x teilt: x/a.
Die gesuchte Wurzel muss zwischen diesen beiden Faktoren liegen, also wird das neue
x als Mittelwert aus x und x/a berechnet:
xn+1= (xn + a/xn)/2

-
Berechnung der Nullstelle einer Funktion nach dem Newton-Verfahren:
Bilde an einem beliebigen Startwert x der zu untersuchenden Funktion die Tangente
an die Kurve. Berechne den Schnittpunkt dieser Tangente mit der x-Achse. Dieser
Wert ist das neue x. Bilde wieder die Tangente...

Allgemein lässt sich zeigen, dass gilt xn+1 = xn - f(x)/f'(x)
Dies ist die allgemeinere Form des Herons-Verfahrens, denn um die Wurzel aus a
zu suchen, muss man die Gleichung x2 - a = 0 lösen:
Das lässt sich mit dem Newtonverfahren für f(x) = x2 - a berechnen:
xn+1 = xn -
(xn2 - a)/(2xn) =
xn/2 + a/(2xn)
Also lässt sich die allgemeinere Wurzel ziehen, indem man die Gleichung
xb - a = 0 mit dem Newtonverfahren löst:
xn+1 = xn
- xnb/(b*xnb-1)
b in [2; 3; ... ]
Für die oben genannten Strukturen ist ein Computer gut geeignet, da er fest vorgegebene Operationen in sehr kurzer Zeit berechnen kann ("Rechenknecht").
Für das strukturierte Programmieren von Wiederholungen sind drei Typen von "Schleifen" vorgesehen:
- Feste Anzahl von Wiederholungen: for-Schleife
Eine for-Schleife besteht normalerweise aus einem Zähler, der in einem bestimmten
Intervall hoch- oder heruntergezählt wird. Für jedem Zählvorgang wird die Schleife
einmal durchlaufen. Die Schleife ist beendet, wenn die Zählvariable ihr Intervall
verlassen hat.
- Abbruchbedingung am Anfang der Schleife: while-Schleife

In diesem Fall testet der Computer zur Laufzeit, ob eine Bedingung erfüllt ist. Wenn
ja, dann wird der Schleifenkörper durchlaufen, ansonsten springt er hinter den
Schleifenkörper.
- Abbruchbedingung am Ende der Schleife: do-Schleife

Der Schleifenkörper wird auf jeden Fall einmal durchlaufen. Am Ende wird die
Abbruchbedingung getestet.
Zu beachten ist, dass die letzten zwei Schleifentypen dazu führen können, dass sich das Programm nicht mehr legal beenden lässt. Wenn im Schleifenkörper niemals eine Änderung der Abbruchbedingung stattfindet, dann wird der Schleifenkörper immer und immer wieder durchlaufen!
-
Berechnung der Wurzel nach dem Heron-Verfahren.
final double genauigkeit = 0.001;
InOut.write("Bitte Radikand eingeben:");
double radikand = InOut.readDouble();
double x = 1;
while ( Math.abs( x*x - radikand ) > genauigkeit ) {
x = ( x + radikand/x )/2;
InOut.writeln( "Neuer Wert: "+x );
}
-
Berechnung von π mit der Leibnizreihe.
double sum = 0; double dsum;
int i;
for (i=0; i<200; i++){
dsum = (double)(1/(2.0*i + 1.0));
if (i%2 == 0) sum = sum + dsum;
else sum = sum - dsum;
}
InOut.writeln( " Ergebnis: "+4.0*sum );
-
Berechnung von π mit dem Algorithmus von "Tamura" und "Kannada":
A=X=1; B=1/(Wurzel 2); C=1/4;
loop: Setze Y = A;
Setze A = (A+B)/2;
Setze B = Wurzel( B*Y );
Setze C = C - X(A-Y)²;
Setze X = 2X
Gib aus: (A+B)²/4C
Gehe zum loop
double A, B, C, X, Y; int i;
A=X=1;
B=1/Math.sqrt(2); C=0.25;
for (i=0; i<5; i++){
Y=A;
A=(A+B)/2;
B=Math.sqrt(B*Y);
C=C-X*(A-Y)*(A-Y);
X=2*X;
InOut.writeln( "Ergebnis: "+(A+B)*(A+B)/(4*C) );
}
Dieses Verfahren "konvergiert" im Gegensatz zur Leibnizriehe extrem schnell gegen π.
Besonders gut lässt sich die Wirkung von Schleifen in Verbindung mit grafischen Ausgaben zeigen. In einem ersten Beispiel sollen Kreise auf der Winkelhalbierenden eines Fensters ausgegeben werden.
Hier der entsprechende Quelltext in Java unter Verwendung des Paketes mygraphics:
import java.awt.*;
import mygraphics.*;
class RRWindow extends GraphicFrame {
public void paint(Graphics g) {
super.paint(g);
final int d = 20;
int i;
for (i=0; i<10; i++){
g.drawOval(i*d,i*d,d,d);
}
}
}
class TestWindow {
public static void main(String args[]){
System.out.println("Starting TestWindow...");
RRWindow fenster = new RRWindow();
}
}
Das Programm beschreibt zwei Klassen:
-
Die Klasse RRWindow:
Hier wird beschrieben, was in einem "RRWindow"-Fenster gezeichnet werden soll, falls
es jemand verwendet.
-
Die Klasse TestWindow:
Hier steht in "main" wie üblich das Hauptprogramm (deshalb muss der Dateiname in diesem
Fall auch "TestWindow" heißen).
Das Hauptprogramm gibt eine kurze Meldung aus und erzeugt dann ein "RRWindow".
Um Grafik auszugeben wird also ein Fenster benötigt, dem man in einem "paint"-Abschnitt erklärt, was zu zeichnen ist und ein Hauptprogramm das so ein Fenster erzeugt...
"Es gibt kein Zahlentripel, das die Gleichung xn + yn = zn erfüllt, wenn n größer als 2 ist."
Pierre de Fermat behauptet in seinen Aufzeichnungen, dass er einen wahrhaft wunderbaren Beweis dafür gefunden hätte, der Rand auf dem er schreibe für seine Aufzeichnungen jedoch zu klein sei.
Um sich der Untersuchung dieses Satzes zu nähern, kann man sich mit dem Satz des Pythagoras beschäftigen:
x2+y2 = z2
In einem einfachen Programm suchen wir "pythagoräische Zahlentripel", also jeweils drei Zahlen, die diese Gleichung erfüllen:
int x, y, z;
for (x = 1; x < 1000; x++){
for (y = 1; y < 1000; y++){
for (z = 1; z < 1000; z++){
if (x*x + y*y == z*z) InOut.writeln( "x = "+x+" y = "+y+" z = "+z );
}
}
}
Ausgabe:
x = 3 y = 4 z = 5
x = 4 y = 3 z = 5
x = 5 y = 12 z = 13
x = 6 y = 8 z = 10
x = 8 y = 6 z = 10
x = 9 y = 12 z = 15
x = 12 y = 5 z = 13
x = 12 y = 9 z = 15
...
Dieser Quelltext kann noch optimiert werden. Da sowohl 32+42=52
, als auch 42+32=52
(Kommutativität der Addition), reicht es wenn y nur bis x läuft.
Außerdem ist z sicher größer als x, denn es wird eine positive Quadratzahl dazuaddiert. Deshalb ergibt sich die folgende Variante:

"Der Tresor geht nur auf, wenn Schalter 1 nicht wie Schalter 2 steht, Schalter 3 aus ist und von Schalter 1 und Schalter 3 mindestens einer an ist."

Kodierung wird normalerweise benötigt, um Daten auf eine spezielle Weise zu übertragen, oder zu speichern. Beispielsweise tragen die Lebensmittel, die von der Kasse registriert werden einen Code, den sogenannten EAN-Code (Europäische Artikel-Nummerierung). Wie kann man es erreichen, dass der Leser des Codes feststellt, ob er Ziffern fehlerhaft oder vertauscht erkannt hat?
Wenn Vertauschungen als Fehler ausscheiden, dann hilft die Bildung einer Prüfsumme. Dabei werden alle Ziffern des Codes addiert. Anschließend wird diejenige Ziffer an den Code angehängt, die die Summe zu einem Vielfachen von 10 ergänzt. Soll beispielsweise die Zahl
7 3 0 4 9 1 9 3
übertragen werden, so wird zuerst die Summe gebildet:
7 + 3 + 0 + 4 + 9 + 1 + 9 + 3 = 36
Die nächste durch 10 teilbare Zahl ist 40. Deshalb müsste als Prüfziffer eine 4 angehängt werden:
7 3 0 4 9 1 9 3 4
Auf diese Weise werden die meisten Fehler erkannt, das Verfahren selbst ist allerdings auch nicht fehlerfrei. Es können immer noch fehlerhafte Daten als richtig erkannt werden und korrekte Daten als fehlerhaft.
Um auch die Vertauschung von Ziffern zu erkennen, werden die einzelnen Ziffern gewichtet. Ein sehr einfaches Verfahren dieser Art wird beim EAN-Code verwendet: jede erste Ziffer wird mit 1 gewichtet, jede zweite mit 3. In unserem Beispiel:
7·1 + 3·3 + 0·1 + 4·3 + 9·1 + 1·3 + 9·1 + 3·3 = 58
Auch hier ergibt sich die Kontrollziffer durch Ergänzung zum nächsten Vielfachen von 10 (in unserem Beispiel also eine 2)
Dieser Code erkennt allerdings nicht alle Vertauschungen. In 10% aller Fälle, nämlich bei 0 und 5, 1 und 6, 2 und 7, 3 und 8 und 4 und 9 ergeben die vertauschten Ziffern die gleiche Prüfsumme.
Algorithmus zur Bestimmung der Prüfziffer:

- Schreiben Sie ein Programm/Struktogramm, das den letzten Satz von Fermat für x, y, z < 1000 und
n = 3 überprüft
- Erweitern Sie das Programm von oben, indem Sie zusätzlich n von 3 bis 6 laufen lassen.
- Erraten Sie, was der Algorithmus dieses Struktogramms berechnet: