Dienstag, 15. Oktober 2013

Binomialkoeffizient berechnen

In diesem Post möchte ich fertigen Code zum Berechnen des Binomialkoeffizientens vorstellen, welcher z.B. in der Kombinatorik ein wichtiges Hilfsmittel ist.
Der Binomialkoeffizient zweier Zahlen n und k wird dargestellt als

und berechnet sich zu n!/(k! * (n-k)!), wobei x! die Fakultät bezeichnet.
Anstatt diese Formel direkt in C# umzusetzen, berechne ich zuerst den Teil n!/k! = n * (n - 1) * ... * (k + 1), was die benutzten Zahlen wesentlich verkleinert, die Geschwindigkeit erhöht und Überläufe erst später auftreten lässt.
Der Code, ich benutzte die Funktion Factorial() aus dem vorigen Post zur Fakultätsberechnung:

        public ulong BinC(ulong n, ulong k)
        {
            if (n < k)
                return 0;

            ulong Numerator = 1;
            for (ulong i = n; i > k; i--)
            {
                Numerator *= i;
            }
            ulong Demoninator = Factorial(n - k);
            return (Numerator / Demoninator);
        }

        public ulong Factorial(ulong n)
        {
            ulong Result = 1;
            for (ulong i = 1; i <= n; i++)
            {
                Result *= i;
            }
            return Result;
        }

1 Kommentar:

  1. Hi, erst mal danke für den Code. Aber warum kommt bei BinC(24,6) der Wert 4 raus? Oder muss etwas bestimmtes beachte werden? Danke fürs Feedback und VG

    AntwortenLöschen