ApCoCoA-1:Examples Tutorial De Euklid

From ApCoCoAWiki
Revision as of 20:13, 17 July 2008 by StK (talk | contribs)

Euklidischer Algorithmus

Wenn wir auf der Suche nach dem größten gemeinsamen Teiler Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mbox{ggT}\left(A,B\right)} zweier (ganzer) Zahlen und 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.