Logo des digitalen Schulbuchs inf-schule.de. Schriftzug in Zustandsübergangsdiagramm eines endlichen Automaten.

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.

Kira: Das kann lange dauern. Ich habe insgesamt 63 Personen eingeladen. Karim: Bei mir kommen nochmal 48 Personen dazu. Hoffentlich ist die Fete nicht vorbei, wenn alle sich begrüßt haben.

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.

<Black-Box-Diagramm><Funktionsname>anzahlBegruessungen</Funktionsname><Übergaben><Übergabe><Wert>113</Wert><Variable>anzahlPersonen</Variable><Typ>int</Typ></Übergabe></Übergaben><Rückgabe><Typ>int</Typ><Wert>...</Wert></Rückgabe></Black-Box-Diagramm>

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.

Begrüßungen bei 1 Person

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

anzahlBegruessungen(1) = 0

Die 2. Person kommt zur Party.

Begrüßungen bei 2 Personen

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.

Begrüßungen bei 3 Personen

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.

Begrüßungen bei 4 Personen

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?

X

Fehler melden

X

Suche