Verallgemeinerung
Die Berechnungen verallgemeinern
Beim Durchspielen der Begrüßungen sind wir zu folgenden Berechnungen gelangt.
anzahlBegruessungen 1 -> 0 anzahlBegruessungen 2 -> (anzahlBegruessungen 1) + 1 -> 0 + 1 -> 1 anzahlBegruessungen 3 -> (anzahlBegruessungen 2) + 2 -> 1 + 2 -> 3 anzahlBegruessungen 4 -> (anzahlBegruessungen 3) + 3 -> 3 + 3 -> 6 ...
Diese lassen sich so verallgemeinern:
Rekursionsanfang bzw. Rückführungsanfang:
Falls anzahlPersonen == 1:
anzahlBegruessungen anzahlPersonen -> 0
Rekursionsschritt bzw. Rückführungsschritt:
Falls anzahlPersonen > 1:
anzahlBegruessungen anzahlPersonen -> anzahlBegruessungen (anzahlPersonen - 1) + anzahlPersonen - 1
Aufgabe 1
Erläutere die Verallgemeinerung der Berechnungen mit Hilfe eines Rekursionsanfangs und eines Rekursionsschritts.
Die verallgemeinerten Berechnungen implementieren
Für die Funktion anzahlBegruessungen
kann man mit Hilfe des Rekursionsanfangs und des Rekursionsschritts
die folgende Funktionsdefinition erstellen. Beachte, dass die Funktion im Funktionsausdruck selbst aufgerufen wird.
Es handelt sich um eine rekursive Funktionsdefinition.
anzahlBegruessungen: Int -> Int
anzahlBegruessungen anzahlPersonen =
if anzahlPersonen == 1 then
0
else
anzahlBegruessungen (anzahlPersonen - 1) + anzahlPersonen - 1
Aufgabe 2
- Erkläre den Aufbau der Funktionsdefinition.
- Teste die Funktionsdefinition in der REPL.
Aufgabe 3
Löse mit Hilfe der Funktion das Ausgangsproblem:
Wenn alle eingeladenen Gäste zur Fete kommen, dann sind das - zusammen mit dir - 126 Personen. Wie viele Begrüßungen werden dann stattfinden, wenn tatsächlich jeder jeden begrüßt?