Beispiel - Das Begüßungsproblem

Jeder begrüßt jeden

Kira und Karim werden demnächst 18 Jahre alt. Ihre Freunde sind zu einer riesigen Fete eingeladen. Damit alle sich kennenlernen, soll jeder jeden erst einmal begrüßen.

Wenn alle eingeladenen Gäste zur Fete kommen, dann sind das - zusammen mit Kira und Karim - 113 Personen. Wie viele Begrüßungen werden dann stattfinden, wenn tatsächlich jeder jeden begrüßt?

Aufgabe 1

Wie viele Begrüßungen finden hier statt? Hast du bereits eine Idee, wie man diese Anzahl berechnen könnte?

Ein Berechnungsverfahren

Ziel ist es, ein Berechnungsverfahren für die Funktion anzahlBegruessungen zu entwickeln. Bei Übergabe der Anzahl der Personen soll diese Funktion die Anzahl der erforderlichen Begrüßungen bestimmen und zurückgeben.

Wir spielen die Begrüßungen (in Gedanken) einmal durch. Wir nehmen dabei an, dass die Personen alle der Reihe nach zur Fete kommen.

Die 1. Person kommt zur Party.

Diese Person muss niemanden begrüßen. Es gilt also:

anzahlBegruessungen(1) = 0

Die 2. Person kommt zur Party.

Diese Person muss nur eine Person begrüßen. Für die Gesamtanzahl der Begrüßungen gilt:

anzahlBegruessungen(2) = anzahlBegruessungen(1) + 1 = 0 + 1 = 1

Die 3. Person kommt zur Party.

Diese Person muss jetzt 2 Personen begrüßen. Für die Gesamtanzahl der Begrüßungen gilt:

anzahlBegruessungen(3) = anzahlBegruessungen(2) + 2 = 1 + 2 = 3

Die 4. Person kommt zur Party.

Diese Person muss bereits 3 Personen begrüßen. Für die Gesamtanzahl der Begrüßungen gilt:

anzahlBegruessungen(4) = anzahlBegruessungen(3) + 3 = 3 + 3 = 6

Aufgabe 2

(a) Ergänze die nächste Berechnungsformel:

anzahlBegruessungen(5) = ...

(b) Verallgemeinere jetzt die Berechnungsformel:

anzahlBegruessungen(anzahlPersonen) = ...

Implementierung des Berechnungsverfahrens

Die Funktion anzahlBegruessungen lässt sich direkt mit der entwickelten Berechnungsformel implementieren.

Aufgabe 3

(a) Teste die Funktion mit verschiedenen Funktionsaufrufen. Bestimme auch die gesuchte Anzahl bei 113 Personen.

(b) Hier eine mit Ausgaben angereicherte Implementierung der Funktion anzahlBegruessungen:

Erkläre, wie die Ausgaben bei der Berechnung von Funktionswerten zustande kommen.

(c) In der Funktionsdefinition der Funktion anzahlBegruessungen kommt keine Wiederholeanweisung vor. Trotzdem wird hier eine Berechnung wiederholt durchgeführt. Erläutere, wie diese wiederholte Berechnung hier zustande kommt.

(d) In der Funktionsdefinition der Funktion anzahlBegruessungen kommt eine Fallunterscheidung vor. Erläutere, wozu diese Fallunterscheidung benötigt wird.