Euklidischer Algorithmus

http://www.dreamincode.net/code/snippet280.htm

gcd ... greatest common divisor = ggT

ansich das gleiche wie beim code von "fytzi" nur ein bissl langsamer. den pseudo-code solltest du leicht in C gieszen koennen.

ggT(a, b)
{
   if a < b: dreieckstausch(a,b)
   rest = a % b
   if rest == 0: return b
   else: return ggT(b, rest)
}

[edit]
wikipedia hat natuerlich auch einen berg an pseudo-code dazu:
http://de.wikipedia.org/wiki/Euklidischer_Algorithmus
[/edit]

Zitat von huberer98

ich habe mich schon zu tode gegoogelt, aber leider nichts gefunden!

Also das glaub ich dir beim besten Willen nicht.
Das erste Ergebnis, das Google ausspuckt: http://de.wikipedia.org/wiki/Erweitert…ische_Umsetzung

...also bitte bemüh dich etwas. Fertiger C-Code wird hier nur ungern weitergegeben. Und selbst den würdest du ohne weiters bei Google finden. Oder hast du eine konkrete Frage?

Zitat von huberer98

Ob dus glaubst oder nicht: Den Beitrag habe ich auch als erstes gefunden und auch umgesetzt. Ich wollte eig. wissen wie man den erweiterten Euklidischen Algorithmus programmiert.

Das ist mir schon bewusst, aber wie gesagt, den findest du ohne weiteres bei Google.

Zitat von huberer98

Und in Google habe ich nur Codes ind Java und HTML gefunden. da ich keine ahnung von diesen beiden Sprachen habe nutzen die mir dehr wenig.

:applaus::applaus::applaus::applaus::applaus: :rofl::rofl::rofl::rofl::rofl::rofl::lol::lol:
...

Zitat von huberer98

Aber mitlerweile hat sich das Problem eh schon erledigt, da ich das projekt einfach aufggeben habe. ich hatte einfach keine lust mehr von dem Euklid. Alg.!

Ja, ich verstehe dich schon. Dass du bei so einem komplizierten und schwierigen Projekt aufgibst, war abzusehen. Nur die besten verstehen den Eudklidschen Algorithmus, der ja so schlecht dokumentiert ist und überhaupt nicht weit verbreitet.
Unser Programmierlehrer war ja wahnsinnig, uns diesen Algorithmus in Form von Pseudo-Code bereits in der zweiten Stunde vorzusetzen, wo wir alle noch keine Ahnung von irgendeiner Programmiersprache hatten.

abc

hi,

hab hier den einfachen erweitterten euklid. algorithmus mal gemacht, der erweiterte geht aber im prinzip genauso.
der ttrick dabei ist eigentl. nur dass du wenn du quasi die neuen variablen anhand der alten zuweist.

#include<stdio.h>


unsigned int euklid(int x,int y);
unsigned int x, y, z, a, b, c=1;


int main(void) 
{
    printf("Dieses Programm dient zur Berechnung des euklidischen Algorithmus!\n\nBitte geben sie die erste Zahl ein: ");
    scanf("%u", &x);
    printf("Bitte geben sie die zweite Zahl ein:");
    scanf("%u", &y);

    if(x<y) {
           z=x;
           x=y;
           y=z;
       }


    printf("Der groesste gemeinsame Teiler von %u und %u ist %u!\n", x, y, euklid(x,y));
    return 0;
}






unsigned int euklid(int x,int y) 
{
    a=x;
    b=y;

       do {
          c= a % b;
          a= b;
          b= c;
          }
       while(c>0);
       return a;
}