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.

def anzahlBegruessungen(anzahlPersonen):
    if anzahlPersonen < 2:
        ergebnis = 0
    else:
        ergebnis = anzahlBegruessungen(anzahlPersonen-1) + (anzahlPersonen-1)
    return ergebnis

Aufgabe 3

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

>>> anzahlBegruessungen(4)
6
>>> anzahlBegruessungen(113)
...

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

def anzahlBegruessungen(anzahlPersonen):
    print('berechne anzahlPersonen('+str(anzahlPersonen)+')')
    if anzahlPersonen < 2:
        ergebnis = 0
    else:
        ergebnis = anzahlBegruessungen(anzahlPersonen-1) + (anzahlPersonen-1)
    print('liefere '+str(ergebnis))
    return ergebnis

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

>>> anzahlBegruessungen(4)
berechne anzahlPersonen(4)
berechne anzahlPersonen(3)
berechne anzahlPersonen(2)
berechne anzahlPersonen(1)
liefere 0
liefere 1
liefere 3
liefere 6
6

(c) In der Funktionsdefinition der Funktion anzahlBegruessungen kommt keine Wiederholeanweisung vor. Trotzdem wird hier eine Berechnung wiederholt durchgeführt. Wie wird diese wiederholte Berechnung hier beschrieben?

(d) In der Funktionsdefinition der Funktion anzahlBegruessungen kommt eine Fallunterscheidung vor. Wozu wird diese Fallunterscheidung benötigt?