Achilles und die Schildkröte
Reihen
Iterationen
Wiederholungen
Beispiele in Java
Grafische Beispiele und verschachtelte Schleifen
Der Satz von Fermat
Logikrätsel
Fehlererkennender Code
Aufgaben

« Achilles und die Schildkröte

« Reihen

• 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)ⁿ · 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 - x³/3! + x⁵/5! - x⁷/7! + ...
  
  

« Iterationen

• 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:
  
  x_n+1= (x_n + a/x_n)/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 x_n+1 = x_n - f(x)/f'(x)
  
  Dies ist die allgemeinere Form des Herons-Verfahrens, denn um die Wurzel aus a zu suchen, muss man die Gleichung x² - a = 0 lösen:
  Das lässt sich mit dem Newtonverfahren für f(x) = x² - a berechnen:
  x_n+1 = x_n - (x_n² - a)/(2x_n) = x_n/2 + a/(2x_n)
  Also lässt sich die allgemeinere Wurzel ziehen, indem man die Gleichung x^b - a = 0 mit dem Newtonverfahren löst:
  
  x_n+1 = x_n - x_n^b/(b*x_n^b-1)
  b in [2; 3; ... ]
  
  

« Wiederholungen

• 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.

« Beispiele in Java

• 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 π.

« Grafische Beispiele und verschachtelte Schleifen

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();

  }



}

  

• 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".

« Der letzte Satz von Fermat

"Es gibt kein Zahlentripel, das die Gleichung xn + yn = zn erfüllt, wenn n größer als 2 ist."

x2+y2 = z2

    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 );

        }

      }

    }

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

 ...

« Logikrätsel

« Fehlererkennender Code

« Aufgaben

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