Euklid

Euklidischer Algorithmus zur Bestimmung des größten gemeinsamen Teilers zweier Zahlen


Beispiel 1:

Bestimme den größten gemeinsamen Teiler von 225 und 60!

Zahl1 : Zahl2 = Ergebnis der
Ganzzahldivision
("Vielfaches")		   Rest
225 : 60 = 3 Rest 45
60 : 45 = 1 Rest 15
45 : 15 = 3 Rest 0

15 ist der größte gemeinsame Teiler!

Das Verfahren bricht also ab, wenn der Rest gleich Null ist. Der größte gemeinsame Teiler ist der in dem Moment aktuelle Wert der Zahl2.

verbaler Entwurf
  1. Eingabe der beiden Zahlen
  2. Berechnung mit folgenden Operationen:
    1. Ermittlung des Restes
    2. Zahl1 bekommt den Wert von Zahl2
    3. Zahl2 bekommt den Wert des Restes
    4. Durch Verwendung einer Schleife werden die Schritte 2.1 bis 2.3 wiederholt.
  3. Ausgabe des Ergebnis (Zahl1)


Übungen
  1. Ermittle mit einer Tabelle, wie oben angegeben, den ggT zweier anderer Zahlen!
    Was passiert, wenn Zahl1 kleiner als Zahl2 ist?
  2. Warum muss vom Programm Zahl1 als Ergebnis ausgegeben werden und nicht wie im obigen Beispiel Zahl2?
  3. Stelle den Algorithmus in einem Struktogramm dar!
  4. Implementiere eine Applikation, die den ggT zweier Zahlen nach diesem Verfahren bestimmt!