Informatik
Startseite > Unterricht > Algorithmen und Datenstrukturen > Rekursion
Beispiel 1: Gezähltes Händeschütteln
Aufgabe: Auf einer Geburtstagsgesellschaft sind n Gäste anwesend. Jede Person gibt jeder anderen genau einmal die Hand. Welches ist die Häufigkeit des Händeschüttelns h(n) in Abhängigkeit von n?
Lösung: Wir verfahren gemäß der Maxime "Führe die Aufgabe auf eine einfachere Version ihrer selbst zurück!" Das heißt, wir bestimmen h(n) dadurch, dass wir annehmen, h(n - 1) sei bereits bekannt - und nun trifft der n-te Gast ein. Die Hand wie vieler Personen muss er schütteln? Natürlich die von n - 1 Personen. Also gilt h(n) = h(n - 1) + n - 1.
Welches ist der unmittelbar lösbare Fall? Das ist h(1) = 0, denn eine Person kann niemand anderem die Hand schütteln.
Also gilt:
h(n) = wenn n = 1 dann 0 sonst h(n - 1) + n - 1.
In Java:
static int h (int n) {
if (n <= 1)
return 0;
else
return h(n - 1) + n - 1;
} // Ende hDas Gesamtprogramm lautet:
import java.io.*;
class Hände {
// demonstriert lineare Rekursionstatic int h (int n) {
if (n <= 1)
return 0;
else
return h(n - 1) + n - 1;
} // Ende hstatic void main (String xy[]) throws IOException {
InputStreamReader lies = new InputStreamReader(System.in);
BufferedReader eing = new BufferedReader(lies);System.out.println("\nGezaehltes Haendeschuetteln");
System.out.println("------------------------\n");System.out.print("Anzahl der Gäste: ");
int gästezahl = Integer.parseInt(eing.readLine());System.out.println("h(" + gästezahl + ") = " + h(gästezahl));
} // Ende main
} // Ende HändeBeispieldialog:
> java Hände
Gezaehltes Haendeschuetteln
-----------------------------------------Anzahl der Gäste: 10
h(10) = 45