Alle Herausforderungen
Mittel 0 gelöst 0% Erfolgsquote

Fixpunktfreie Permutationen (Derangements)

Zähle die Anordnungen von n Elementen, bei denen keines an seinem ursprünglichen Platz bleibt.

Das lernst du

  • Aus einer Abzählüberlegung eine Rekursionsformel gewinnen
  • Eine Rekursionsformel ausgehend von den Anfangswerten iterieren
  • Die Fälle n = 0 und n = 1 behandeln

Problem

Fünf Freunde werfen ihre Hüte auf einen Haufen, und jeder nimmt sich zufällig einen zurück. Auf wie viele Arten kann es passieren, dass niemand seinen eigenen Hut bekommt? Eine Anordnung von n Elementen, bei der kein Element an seiner ursprünglichen Position bleibt, heißt fixpunktfreie Permutation oder Derangement. Die Anzahlen beginnen mit 1, 0, 1, 2, 9, 44 und folgen der Formel D(n) = (n − 1) × (D(n − 1) + D(n − 2)).

Implementiere derangements(n).

Eingabe

n: Die Anzahl der Elemente.

Ausgabe

Gib die Anzahl der fixpunktfreien Permutationen von n Elementen zurück. D(0) ist 1 (die leere Anordnung bewegt nichts, was an seinem Platz bleiben könnte), und D(1) ist 0.

Einschränkungen

0 ≤ n ≤ 20

Beispiele

Beispiel 1
Eingabe:
n = 3

Erwartete Ausgabe:
expected = 2
Eingabe:
long long n = 3;

Erwartete Ausgabe:
long long expected = 2;
Eingabe:
long n = 3;

Erwartete Ausgabe:
long expected = 2;

Erläuterung

Bei den Elementen A, B, C bewegen nur BCA und CAB jedes Element, also lautet die Antwort 2.

Beispiel 2
Eingabe:
n = 4

Erwartete Ausgabe:
expected = 9
Eingabe:
long long n = 4;

Erwartete Ausgabe:
long long expected = 9;
Eingabe:
long n = 4;

Erwartete Ausgabe:
long expected = 9;

Erläuterung

D(4) = 3 × (D(3) + D(2)) = 3 × (2 + 1) = 9.

So gehst du vor

Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.

Hinweis 1

Beginne mit D(0) = 1 und D(1) = 0.

Hinweis 2

Jeder neue Wert ergibt sich aus den beiden vorherigen und dem aktuellen n.

Hinweis 3

Man braucht immer nur die letzten beiden Werte.

Erwartete Komplexität

Zeit O(n), zusätzlicher Speicher O(1)

Referenzen

Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.

Die beste bestandene Lösung jedes Coders. Schnellere, sparsamere und besser bewertete Lösungen stehen weiter oben.

Noch keine bestandene Lösung. Löse sie und hol dir Platz eins.

Von anderen lernen

Community-Lösungen

Noch keine veröffentlichten Lösungen. Löse die Aufgabe und teile als Erster eine Lösung.