Читать книгу Algorithmen und Datenstrukturen - Gunter Saake - Страница 78
Beispiel 3.9 Größter gemeinsamer Teiler ggT
ОглавлениеBerechnet wird der größte gemeinsamer Teiler ggT zweier natürlicher Zahlen.
Für x > 0 und y > 0 gelten folgende Zusammenhänge:
| ggT(x, x) | = | x |
| ggT(x, y) | = | ggT(y, x) |
| ggT(x, y) | = | ggT(x, y − x) für x < y |
Basierend auf diesen Gesetzmäßigkeiten, können wir folgenden applikativen Algorithmus formulieren:
| ggT(x, y) = | if (x ≤ 0) ∨ (y ≤ 0)then ggT(x, y) else | |
| if x = y | then x else | |
| if x > y | then ggT(y, x) | |
| else ggT(x, y − x) fi fi fi |
Die definierte Funktion ggT ist korrekt für positive Eingaben, bei negativen Eingaben und Null ergeben sich nicht abbrechende Berechnungen (partiell undefinierte Funktion).
Die folgende Beispielauswertung verdeutlicht die Arbeitsweise des applikativen Algorithmus:
| ggT(39, 15) | ggT(15, 39) ggT(15, 24) | |
| ggT(15, 9) ggT(9, 15) ggT(9, 6) | ||
| ggT(6, 9) ggT(6, 3) ggT(3, 6) | ||
| ggT(3, 3) 3 |
Dieses Schema ist eine Formalisierung des Originalverfahrens von Euklid (Euklid: Elemente, 7. Buch, Satz 2; ca. 300 v.Chr.).
Das folgende Beispiel demonstriert den Einsatz mehrerer Funktionen in einem applikativen Algorithmus:
