Как рассчитать биномиальные коэффициенты для больших чисел

Question

Мне нужно рассчитать n!/(n-r)!r! в C #. Это легко вычислить, используя функцию факториала для небольших чисел, но когда число становится больше, чем 100, это не работает. Есть ли другой способ, которым мы можем вычислить комбинации для больших чисел?

Answer 1

Прежде всего, я отмечаю, что вы пытаетесь вычислить биномиальный коэффициент, поэтому назовем его так.

Вот несколько способов сделать это.Если вы используете BigInteger, вам не нужно беспокоиться о переполнении:

Первый метод: используйте factorial:

static BigInteger Factorial(BigInteger n)
{
    BigInteger f = 1;
    for (BigInteger i = 2; i <= n; ++i)
        f = f * i;
    return f;
}

static BigInteger BinomialCoefficient(BigInteger n, BigInteger k)
{
    return Factorial(n) / (Factorial(n-k) * Factorial(k));
}

Второй метод: используйте рекурсию:

static BigInteger BinomialCoefficient(BigInteger n, BigInteger k)
{
    if (n == 0) return 1;
    if (k == 0) return 0;
    return BinomialCoefficient(n-1, k-1) + BinomialCoefficient(n-1, k)
}

Thisметод, однако, не быстрый, если вы не запомните результат.

Метод третий: будьте более умны в отношении минимизации количества умножений и раннего деления.Это позволяет сохранять малые числа:

static BigInteger BinomialCoefficient(BigInteger n, BigInteger k)
{
    // (n C k) and (n C (n-k)) are the same, so pick the smaller as k:
    if (k > n - k) k = n - k;
    BigInteger result = 1;
    for (BigInteger i = 1; i <= k; ++i)
    {
        result *= n - k + i;
        result /= i;
    }
    return result;
}

Так, например, если вы вычисляли (6 C 3) вместо вычисления (6 x 5 x 4 x 3 x 2 x 1) / ((3 x 2)x 1) x (3 x 2 x 1)), вы вычисляете (((4/1) * 5) / 2) * 6) / 3, что по возможности сохраняет небольшие числа.

Answer 2

Следуя тому, что сказал Эрик, раннее деление очень помогает, вы можете улучшить это, разделив от высокого до низкого Таким образом, вы можете рассчитать любой результат, если конечный результат соответствует Long. Вот код, который я использую (извиняюсь за Java, но преобразование должно быть легким):

public static long binomialCoefficient(int n, int k) {
   // take the lowest possible k to reduce computing using: n over k = n over (n-k)
   k = java.lang.Math.min( k, n - k );

   // holds the high number: fi. (1000 over 990) holds 991..1000
   long highnumber[] = new long[k];
   for (int i = 0; i < k; i++)
      highnumber[i] = n - i; // the high number first order is important
   // holds the dividers: fi. (1000 over 990) holds 2..10
   int dividers[] = new int[k - 1];
   for (int i = 0; i < k - 1; i++)
      dividers[i] = k - i;

   // for every divider there always exists a highnumber that can be divided by 
   // this, the number of highnumbers being a sequence that equals the number of 
   // dividers. Thus, the only trick needed is to divide in reverse order, so 
   // divide the highest divider first trying it on the highest highnumber first. 
   // That way you do not need to do any tricks with primes.
   for (int divider: dividers) 
      for (int i = 0; i < k; i++)
         if (highnumber[i] % divider == 0) {
            highnumber[i] /= divider;
            break;
         }

   // multiply remainder of highnumbers
   long result = 1;
   for (long high : highnumber)
      result *= high;
   return result;
}

Answer 3

Я думаю, что это будет эффективно
Это O (k)

Обратите внимание!/ р!р!просто отменяет последние значения n
, поэтому 7 3

7 x 6 x 5 x 4 x 3 x 2 x 1 
over 
            4 x 3 x 2 x 1 

public static uint BinomialCoeffient(uint n, uint k)
{
    if (k > n)
        return 0;

    uint c = n;
    for (uint i = 1; i < k; i++)
    {
        c *= n - i;
        c /= i + 1;
    }
    return c;
}

Answer 4

Для .net 4.0 и выше используйте класс BigInteger вместо int / long

Для других .net используйте пользовательский класс больших чисел, например, из IntX: http://www.codeplex.com/IntX/