Eine der besten Methoden zur Berechnung des Binomialkoeffizienten, die ich vorgeschlagen habe, ist Mark Dominus . Es ist viel weniger wahrscheinlich, dass größere Werte für N und K überlaufen als bei anderen Methoden.
%Vor% Nur zum Zweck der Vervollständigung: Die Standardbibliothek C math hat Implementierungen von sowohl Γ als auch lnΓ (genannt tgamma und lgamma ), wobei
Γ (n) & amp; gleich; (n-1)!
Die Bibliotheksberechnung ist sicherlich schneller und genauer als das Summieren von Logarithmen. Für viele weitere Informationen, siehe Wikipedia und Mathworld .
Wenn Sie sich Ihren Code anschauen, verwundert es nicht, dass Ihnen der Speicher schnell ausgeht. Ihre Methode divideFactorials ruft die Methode faktoriell auf und verwendet als Argument die Differenz "Zähler-Nenner". Dieser Unterschied ist sehr wahrscheinlich sehr groß nach Ihrem Code und Sie werden in Ihrer faktoriellen Methode in einer sehr langen Schleife stecken.
Wenn es wirklich nur darum geht, nCk zu finden (was ich aufgrund Ihres Kommentars in Ihrem Code vermute), verwenden Sie einfach:
%Vor%Mit dieser Methode läuft man natürlich sehr schnell aus der Reihe, weil eine lange nicht wirklich sehr lange Zahlen unterstützt, also müssen n und k kleiner als 20 sein.
Wenn Sie annehmen, dass Sie tatsächlich mit sehr großen Zahlen arbeiten, könnten Sie Doppel statt Lang verwenden, da die Kräfte immer mehr an Bedeutung gewinnen.
Bearbeiten: Wenn Sie große Zahlen verwenden, können Sie auch die Stirling-Formel verwenden:
Wenn n groß wird ln (n!) - & gt; n * ln (n) - n.
Dies in Code einfügen:
%Vor%Ich schlage nur diese Antwort vor, da Sie sprachunabhängig sagten, der C # -Code wird nur verwendet, um dies zu demonstrieren. Da Sie für n und k große Zahlen verwenden müssen, um dies zu erreichen, schlage ich dies als allgemeine Möglichkeit vor, den Binomialkoeffizienten für große Kombinationen zu finden.
Für Fälle, in denen n und k beide kleiner sind als etwa 200-300, sollten Sie die Antwort von Victor Mukherjee verwenden, wie es genau ist.
Bearbeiten2: Bearbeitete meinen ersten Code.
Tags und Links algorithm c# math combinatorics