Читать книгу Algorithmen und Datenstrukturen - Gunter Saake - Страница 99

Die Berechnung des größten gemeinsamen Teilers in der zweiten Version mittels Division nutzt die ganzzahlige Division und die Modulofunktion zur Bestimmung des Restes bei der Division.

GGT 2:varX,Y,R: int;

inputX,Y;

R:=1;

whileR ≠ 0do

R:=XmodY;X:=Y;Y:=Rod;

outputX

Auch hier betrachten wir einige Berechnungen, um die Vorgehensweise zu verdeutlichen:

Abschließend betrachten wir das Verhalten für negative X oder Y.

Intuitiv ist GGT2 effizienter als die erste Version – doch wie zeigt man eine derartige Eigenschaft?

Das Beispiel des ggT bereitet die spätere detaillierte Betrachtung von Effizienzeigenschaften vor. Der folgende Algorithmus spielt eine ähnliche Rolle bei Überlegungen zur Korrektheit.