nicht angemeldet
Hallo *jiriki*,
Neben Andreas' Lösung kann man auch noch folgende Rekursionsformel verwenden:
a(1) = 0;
a(n) = n * (a(n-1) + a(n-2));
Da kann man recht leicht erkennen, dass das so funktioniert:
Beispiel 5:
Der erste Matrose A hat 4 Möglichkeiten (Matten 2 bis 5).
Nennen wir den Matrosen, auf dessen Matte sich Matrose A legt B.
Matrose B kann sich nun auf die Matte von Matrose A legen. In diesem Fall bleiben 3 Matten und 3 Matrosen übrige und man hat das Problem offensichtlich auf den Fall n = 3 reduziert.
Wenn wir diese Möglichkeit nun ausschließen so kann man die 1. Matte nun Matrose B zuordnen und das Problem so auf den Fall n = 4 reduzieren.
Grüße
Daniel