Erkundung Recursion Tutor

Das Begrüßungsproblem

Auf einer Party sollen sich alle Gäste gegenseitig die Hände schütteln und vorstellen, damit sich alle kennenlernen. Insgesamt sind auf der Party 113 Gäste anwesend. Wie viele Begrüßungen werden stattfinden, wenn sich tatsächlich alle Gäste gegenseitig begrüßen?

Aufgabe

Ein Berechnungsverfahren

Um ein Berechnungsverfahren zu entwickeln für die Anzahl an Begrüßungen, wenn sich n Gäste alle gegenseitig begrüßen, spielen wir die Begrüßungen in Gedanken einmal durch. Dazu nehmen wir an, dass alle Gäste der Reihe nach zur Party kommen.

Die erste Person muss niemanden begrüßen, es gilt also: anzahlBegruessungen(1) = 0.

Kommt die zweite Person hinzu, muss sie die erste Person begrüßen. Es gibt also eine zusätzliche Begrüßung. Insgesamt sind es dann anzahlBegruessungen(2) = anzahlBegruessungen(1) + 1 = 0 + 1 = 1.

Kommt die dritte Person hinzu, muss sie die beiden bereits anwesenden Personen begrüßen. Es gibt also zwei zusätzliche Begrüßungen. Insgesamt sind es dann anzahlBegruessungen(3) = anzahlBegruessungen(2) + 2 = 1 + 2 = 3.

Kommt die vierte Person hinzu, muss sie die drei bereits anwesenden Personen begrüßen. Es gibt also drei zusätzliche Begrüßungen. Insgesamt sind es dann anzahlBegruessungen(4) = anzahlBegruessungen(3) + 3 = 3 + 3 = 6.

Aufgabe2

Aufgabe3

Implementierung der Berechnungsformel

Es lässt sich die folgende Gesetzmäßigkeit erkennen: Die Anzahl der Begrüßungen für n Personen ist die Anzahl der Begrüßungen für n-1 Personen plus n-1. Das können wir in eine rekursive Funktion verpacken.

Das schauen wir uns nun mithilfe des RecursionTutors an. Der RecursionTutor visualisiert rekursive Programme für Python. Zur besseren Übersichtlichkeit kürzen wir die Funktion mit dem Namen anzahl_begruessungen mit `anz_b` ab. Unten ist ein Diagramm für die Visualisierung von anz_b(4) bereits geladen.

Aufgabe 4