Читать книгу Algorithmen und Datenstrukturen - Gunter Saake - Страница 98
Beispiel 3.21 Größter gemeinsamer Teiler (euklidischer Algorithmus)
ОглавлениеZiel ist die Berechnung des größten gemeinsamen Teilers ggT. Die erste Version formulieren wir wie folgt:
GGT 1:varX,Y: int;
inputX,Y;
whileX ≠ Y do
whileX>YdoX:=X-Yod;
whileX<YdoY:=Y-Xodod;
outputX
Die Vorgehensweise verdeutlicht eine Beispielauswertung von ggT(19, 5), bei der wir für jeden Schleifendurchlauf die Werte der Variablen notieren:
| X | Y |
| 19 | 5 |
| 14 | 5 |
| 9 | 5 |
| 4 | 5 |
| 4 | 1 |
| 3 | 1 |
| 2 | 1 |
| 1 | 1 |
Die Berechnung erfolgt im Wesentlichen durch die Subtraktion des jeweils kleineren Parameters.
Die Berechnung allein durch Subtraktion ist nicht sehr effizient, wenn man etwa an das Beispiel ggT(2, 1000) denkt. Wir entwickeln daher eine zweite Variante, die mittels der Division vorgeht.
