12.5 Der ggT - erweiterter Euklidsche Algorithmus
 
Der Algorithmus

 

Das Beispiel zeigt, wie man mit Hilfe des Euklidschen Algorithmus' den ggT(792,75) bestimmt.

Im ersten Schritt fragen wir, wie häufig die zweite Zahl, also 75 ganzzahlig in der ersten, nämlich 792 enthalten ist. Diese Ganzzahldivision liefert 10 und den Rest 42. Im weiteren Verlauf werden wir sehen, dass die Zahl 10 für den weiteren Verlauf unwichtig ist, also getrost vergessen werden kann. Wesentlich ist, wir berechnen 792 mod 75 und das ist 42. Im zweiten Schritt fragen wir: Wie groß ist der Rest, wenn wir 75 ganzzahlig durch 42 teilen. Wir bestimmen also 75 mod 42. Diese Schritte wiederholen sich

Somit berechnen wir nacheinander:

792 mod 75 = 42
75 mod 42 = 33
42 mod 33 = 9
33 mod 9 = 6
9 mod 6 = 3
6 mod 3 = 0

Ist der Rest 0, ist der Algorithmus zu Ende. 3 ist der gesuchte größte gemeinsame Teiler. Da garantiert werden kann, dass der Rest irgendwann 0 ist, sagen wir, der Algorithmus terminiert.
 

  Nach dieser Untersuchung am Beispiel, formulieren wir den Algorithmus allgemein, so dass wir schließlich in Java implementieren können. Auf den Beweis des Algorithmus' verzichten wir und verweisen auf die einschlägige Literatur verwiesen.
 
allgemeine Darstellung Zu bestimmen ist ggT(a,b)
Wir setzen r0=a und r1 = b; und bestimmen
 
1. Schritt r0 mod r1 =: r2
2. Schritt r1 mod r2 =: r3
3. Schritt r2 mod r3 =: r4
i-ter Schritt ri-1 mod ri =: ri+1
n-ter und letzter Schritt. Er ist dadurch gekennzeichnet, dass der Rest 0 ist. rn-1 mod rn = 0

rn ist der gesuchte ggT(a,b)

 

Der Java-Code
int r;
do {
  r = a%b;
  a = b;
  b = r;
} while(b!=0);
//a ist der ggT
Der ggT(a,b) wird bestimmt. Wir verwenden eine do-while-Schleife und vermeiden so eine Initialisierung von r.
r = a%b; realisiert ri-1 mod ri =: ri+1 wobei das i den Schleifendurchgang mitzählt, was im Programm natürlich überflüssig ist. Nachdem der Rest berechnet wurde. Wird in den nächsten beiden Zeilen a = b; und b = r; der nächste Schleifendurchgang vorbereitet, d.h. ri "rutscht" vor  mod und der Rest hinter mod. Diese Vorbereitung geschieht auch dann, wenn sie eigentlich nicht mehr nötig ist, im letzten Durchgang, wenn der Rest 0 ist, deshalb ist der gesuchte ggT in a und nicht wie man im ersten Moment vermuten möchte in b.

 

Download:
GgT3.java
import info1.*;

public class GgT3{

   public static void main(String[] args){

      StoppUhr eineStoppUhr = new StoppUhr();

      int ggT = 1;

      System.out.print("erste Zahl: ");

      int a = Console.in.readInt();

      System.out.print("zweite Zahl: ");

      int b = Console.in.readInt();

      eineStoppUhr.starten();

      int r;                         //1

      do{

         r = a%b;

         a = b;

         b = r;

      } while(b!=0);

      eineStoppUhr.stoppen();

      ggT = a;

      System.out.println(ggT);

      System.out.println(eineStoppUhr);

   }

}

Kommentar zu Zeile //1:
die Variable
r braucht vor einer do..while-Schleife nicht initialisiert zu werden, wenn dies im Schleifenrumpf passiert. Denn eine Schleife dieses Typs wird mindestens einmal durchlaufen und r bekommt mit r = a%b einen Wert garantiert bekommt.
 

Ergebnis

Da die StoppUhr, wie ein Blick in ihren Quelltext verrät, auf Millisekunden genau die Zeit stoppt, ist die Laufzeit von 16,543 Sekunden auf unter 0,001 Sekunden geschrumpft.

 

Die Klasse Mathematik

Download: Mathematik.java

Den Art den ggT zweier Zahlen zu bestimmen schreiben wir als statische Methode in unserer Klasse Mathematik
   public static int ggT(int a, int b){

      int ggT = 1;

      int r;

      do{

         r = a%b;

         a = b;

         b = r;

      } while(b!=0);

      return a;

   }

  Ein kleines Programm testet die neue Methode.
Testklasse

Download:
GgTTest.java

 

import info1.*;

public class GgTTest {



  public static void main (String[] args) {

     System.out.print("1. Zahl: ");

     int a = Console.in.readInt();

     System.out.print("2. Zahl: ");

     int b = Console.in.readInt();

     System.out.println("der ggT("+a+","+b+") ist: "+

                        Mathematik.ggT(a,b));

  }

}
Ausschnitt aus Raffaels "Schule von Athen"

Euklid erläutert Schülern eine Sternform. Raffel hat Euklid als Bramante portraitiert. Bramante war wesentlich an der Erbauung des Peterdoms in Rom beteiligt

zu 12.6 Übungen
zur Startseite www.pohlig.de (C) MPohlig 2003