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