Читать книгу Algorithmen und Datenstrukturen - Gunter Saake - Страница 77
Beispiel 3.8 Produkt nur unter Verwendung der Addition
ОглавлениеZiel ist die Berechnung des Produkts zweier Zahlen nur unter Verwendung der Addition. Wir können dabei folgende Regeln ausnutzen:
| 0 · y | = | 0 |
| x · y | = | (x − 1) · y + y für x > 0 |
| x · y | = | −((−x) · y) für x < 0 |
Diese Regeln lassen sich wieder direkt in einen applikativen Algorithmus umsetzen:
| prod(x, y)= | if x = 0 | then 0 else |
| if x > 0 | then prod(x − 1, y) + y | |
| else −prod(−x, y) fi fi |
Analog ließe sich die Exponentialfunktion auf die Multiplikation zurückführen.
Das folgende Beispiel ist sozusagen der Prototyp aller mathematischen Algorithmen in der abendländischen Geschichte. Es handelt sich um die exakte Formulierung des euklidischen Algorithmus zur Berechnung des größten gemeinsamen Teilers zweier Zahlen.
