Beispiel - Berechnungen zum Begrüßungsproblem

Das Begüßungsproblem

Kira und Kari werden demnächst 18 Jahre alt. Alle ihre Freunde sollen zu einer riesigen Fete kommen. Damit alle sich kennenlernen, soll jeder jeden erst einmal begrüßen.

Kira: "Das kann lange dauern. Ich habe insgesamt 63 Personen eingeladen."

Kari: "Bei mir kommen nochmal 48 Personen dazu. Mit uns beiden sind wir dann 113 Personen. Hoffentlich ist die Fete nicht vorbei, wenn alle sich begrüßt haben."

Aufgabe 1

(a) Bestimme die Anzahl der Begrüßungen, wenn 6 Personen sich zu einer Fete treffen.

(b) Wenn man die Anzahl der Begrüßungen bei 113 Personen bestimmen möchte, dann braucht man hierzu eine Strategie, z.B.: Angenommen, die 113 Personen kommen alle der Reihe nach zur Fete. Die 1. Person muss niemanden begrüßen, die 2. Person muss nur eine Person begrüßen, die 3. Person muss dann 2 Personen begrüßen, die 4. Person muss schon 3 Personen begrüßen usw..". Wie könnte man nach dieser Strategie die gesuchte Anzahl berechnen?

Wiederholte Abläufe

Die Berechnungen zum Begrüßungsproblem sollen automatisiert werden. Ein erster Lösungsansatz könnte so aussehen:

Aufgabe 2

(a) Warum berechnet die oben gezeigte Anweisungsfolge die gesuchte Anzahl von Begrüßungen? Warum ist es geschickt, die Berechnungen wie im gezeigten Programm nicht mit konkreten Zahlen, sondern allgemein mit Variablen anzulegen?

(b) Wie müsste man das Programm ergänzen, um das Begrüßungsproblem für 113 Personen zu lösen? Welche Nachteile hätte ein solches Programm?

Ablaufmodellierung

Der wiederholte Ablauf der Berechnungen lässt sich sehr gut mit einem Flussdiagramm verdeutlichen:

Mit einem Struktogramm kann man die die Ablauflogik weiter strukturieren.:

Aufgabe 3

Erläutere die Diagramme. Begründe, warum sie ein Verfahren zur Bestimmung der Anzahl der Begrüßungen beschreiben.

Implementierung des Verfahrens

Das beschriebene Verfahren lässt sich mit einer while-Anweisung implementieren:

Das animierte Programm setzt die Anzahl der personen auf 4. Überprüfe, ob das ausgegebene Ergebnis stimmt. Vergleiche das Programm auch mit den oben gezeigten Diagrammen.

Aufgabe 4

Bei der Fete von Kira und Kari kam es zu insgesamt 3741 Begrüßungen. Wie viele Personen waren zur Fete gekommen?

(a) Ändere das oben gezeigte Programm so ab, dass es das neue Problem löst. Achte auf die Einrückungen bei der while-Anweisung.

(b) Was ist, wenn jemand die Anzahl der Begrüßungen falsch gezählt hat (z.B. 3739 statt 3741)? Wie reagiert das entwickelte Programm hierauf?