Problem
Der Binomialkoeffizient C(n, k), gelesen „n über k“, gibt an, auf wie viele Arten man k Elemente aus n verschiedenen Elementen auswählen kann, wenn die Reihenfolge keine Rolle spielt. Die Formel n! / (k! (n − k)!) läuft schnell über, wenn man zuerst die Fakultäten berechnet. Baue das Ergebnis deshalb schrittweise auf oder nutze die Regel aus dem Pascalschen Dreieck: C(n, k) = C(n − 1, k − 1) + C(n − 1, k).
Implementiere binomial_coefficient(n, k).
Eingabe
n: Die Anzahl der Elemente.
k: Wie viele Elemente ausgewählt werden.
Ausgabe
Gib C(n, k) zurück. Für k > n gibt es keine Möglichkeit, dann ist das Ergebnis 0.
Einschränkungen
0 ≤ n ≤ 66
0 ≤ k ≤ 100
Beispiele
Eingabe:
n = 5
k = 2
Erwartete Ausgabe:
expected = 10
Eingabe:
long long n = 5;
long long k = 2;
Erwartete Ausgabe:
long long expected = 10;
Eingabe:
long n = 5;
long k = 2;
Erwartete Ausgabe:
long expected = 10;
Erläuterung
Aus 5 Elementen lassen sich 5 × 4 / 2 = 10 Paare bilden.
Eingabe:
n = 6
k = 0
Erwartete Ausgabe:
expected = 1
Eingabe:
long long n = 6;
long long k = 0;
Erwartete Ausgabe:
long long expected = 1;
Eingabe:
long n = 6;
long k = 0;
Erwartete Ausgabe:
long expected = 1;
Erläuterung
Es gibt genau eine Möglichkeit, nichts auszuwählen: 1.
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Fakultäten von Zahlen über 20 passen nicht in 64 Bit, vermeide sie also.
Hinweis 2
Eine Zeile des Pascalschen Dreiecks lässt sich von rechts nach links direkt im selben Array aktualisieren.
Hinweis 3
C(n, k) ist gleich C(n, n − k), und für k > n ist es 0.
Erwartete Komplexität
Zeit O(n · k), zusätzlicher Speicher O(k)
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.