Einfach 0 gelöst 0% Erfolgsquote

Binomialkoeffizient

Zähle, auf wie viele Arten man k aus n Elementen auswählen kann („n über k“).

Das lernst du

  • Kombinationen ohne Fakultäten berechnen
  • Die Regel aus dem Pascalschen Dreieck anwenden
  • Den Fall k größer als n behandeln

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

Beispiel 1
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.

Beispiel 2
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.

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.