Читать книгу 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.

Algorithmen und Datenstrukturen

Подняться наверх