Difference between revisions of "ApCoCoA-1:Examples Tutorial De Euklid"

From ApCoCoAWiki
(New page: ---- Weiter geht's im Kapitel Etwas Aussagen-Logik. ---- Euklid)
 
Line 1: Line 1:
+
== Euklidischer Algorithmus ==
  
 +
Wenn wir auf der Suche nach dem größten gemeinsamen Teiler <math>\mbox{ggT}\left(A,B\right)</math> zweier (ganzer) Zahlen <math>A</math> und <math>B</math> 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.
 +
 +
<code>
 +
  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;
 +
</code>
  
  

Revision as of 20:13, 17 July 2008

Euklidischer Algorithmus

Wenn wir auf der Suche nach dem größten gemeinsamen Teiler 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.