ApCoCoA-1:Examples Tutorial De Euklid

Euklidischer Algorithmus

Wenn wir auf der Suche nach dem größten gemeinsamen Teiler $\text{ggT}(A,B)$ zweier (ganzer) Zahlen $A$ und $B$ sind, so hilft uns entweder scharfes Hinsehen, oder gar Raten. Man kann dies natürlich auch mathematisch angehen, mit Hilfe des Euklidischen Algorithmus, welcher der älteste bekannte nicht-triviale Algorithmus ist. Das Verfahren wurde erstmals von Euklid von Syrakus um 300 v.Chr. in seinem Werk "Die Elemente" beschrieben.

Bei der Implementation des Euklidischen Algorithmus müssen wir wie meistens zuerst die trivialen Fälle abarbeiten, um uns dann dem Kern des Algorithmus zu widmen.

 Define Euklid(A,B);
 // Sicherheirsabfragen
   If Type(A)<>INT OR Type(B)<>INT Then
     Return "Einer der eingegebenen Parameter ist keine ganze Zahl";
   EndIf;
 // Trivialitaeten
   If A=0 Then
     Print "Der ggT lautet "; Abs(B); Print "."; Return;
   EndIf;\
   If B=0 Then
     Print "Der ggT lautet "; Abs(A); Print "."; Return;
   EndIf;
 // Betraege bilden und ggf. umsortieren
   A:=Abs(A);
   B:=Abs(B);
   If A<B Then
     C:=A;
     A:=B;
     B:=C;
   EndIf;
 // Eigentlicher Algorithmus
   Rest:=1;
   While Rest<>0 Do
     Rest:=Mod(A,B);
     A:=B;
     B:=Rest;
   EndWhile;
 // Ausgabe
 Print "Der ggT lautet "; A; Print "."; Return;
 EndDefine;

---

Weiter geht's im Kapitel Etwas Aussagen-Logik.

---