Lektion 47:

Der Euklidische Algorithmus

 Euklid (griechischer Mathematiker, um 325-265 BC) hat ein sehr schönes Verfahren gefunden, um den größten gemeinsamen Teiler (GGT) zweier Zahlen zu finden. Es basiert auf folgendem Trick: Wenn a und b durch x teilbar sind, dann ist auch a%b durch x teilbar.

Eine mögliche Implementierung ist:

int ggt(int a,int b)
{
// a soll größer als b sein
   if(b>a)
      return ggt(b,a);

   if(b!=0)
      return ggt(b,a%b);
   else
       return a;
};

Übung:

Schreiben Sie diese rekursive Funktion in eine iterative Funktion um.

Einsendungen:

Lösungsvorschlag


Falls Ihnen Fehler im Text auffallen oder Sie Verbesserungsvorschläge haben, dann schicken Sie mir bitte eine Mail. Ich werde mich dann sofort darum kümmern.
[aktuelle Version] [inhalt] [index]      [Fehlerkorrektur, Verbesserungsvorschlag]

© Volkard Henkel <volkard@normannia.de>, last update: 08/25/00