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

Beispiel 3.10 Applikativer Algorithmus mit mehreren Funktionen

Оглавление

Realisiert werden soll der Test, ob eine Zahl gerade ist: even (x). Wir bedienen uns wieder einiger mathematischer Regeln:

even(0) = true
odd(0) = false
even(x + 1) = odd(x)
odd(x + 1) = even(x)

Diese Regeln lassen sich nun wie folgt direkt in den gewünschten Testalgorithmus umsetzen:

even(x) = if x = 0 then true else
if x > 0 then odd(x − 1)
else odd(x + 1) fi fi
odd(x) = if x = 0 then false else
if x > 0 then even (x − 1)
else even (x + 1) fi fi

Einen Algorithmus für den Test auf ungerade Zahlen odd erhalten wir einfach durch Vertauschen der Reihenfolge der Funktionsdefinitionen.


Bisher konnten wir jeweils einfache mathematische Regeln direkt in Funktionsterme umsetzen. Dass dieses nicht immer so einfach ist, zeigt das folgende Beispiel: der Primzahltest. Am Beispiel dieses Verfahrens werden wir auch erstmals die Frage des Aufwandes der Berechnung eines applikativen Funktionsaufrufs betrachten und uns Gedanken über die Effizienz eines Verfahrens machen.

Algorithmen und Datenstrukturen

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