Como calcular coeficientes binomiais para números grandes

Question

eu preciso calcular n!/(n-r)!r! em C#.É fácil calcular usando a função fatorial para números pequenos, mas quando o número fica maior, como 100, não funciona.Existe alguma outra maneira de calcular combinações para números maiores?

Answer 1

Em primeiro lugar, observo que você está tentando calcular o coeficiente binomial, então vamos chamá-lo assim.

Aqui estão algumas maneiras de fazer o cálculo.Se você usa BigInteger você não precisa se preocupar com overflow:

Método um:usar fatorial:

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));
}

Método dois:usar recursão:

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)
}

Este método, entretanto, não é rápido, a menos que você memorizar o resultado.

Método três:seja mais inteligente ao minimizar o número de multiplicações e dividir antecipadamente.Isso mantém os números pequenos:

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;
}

Então, por exemplo, se você estivesse computando (6 C 3), em vez de computar (6 x 5 x 4 x 3 x 2 x 1) / ((3 x 2 x 1) x (3 x 2 x 1)), você computa (((4/1) * 5)/2) * 6)/3, que mantém os números pequenos, se possível.

Answer 2

Seguindo o que o Eric disse, dividir cedo ajuda muito, você pode melhorar isso dividindo de alto para baixo.Desta forma você pode calcular qualquer resultado desde que o resultado final caiba em um Long.Aqui está o código que uso (peço desculpas pelo Java, mas a conversão deve ser fácil):

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

Para .net 4.0 e maior, use a classe BigInteger em vez de int/long

Para outro .net, use uma classe de grande número personalizada, por exemplo, do IntX: http://www.codeplex.com/IntX/

Answer 4

Acho que isso será eficiente
Está tudo bem)

observe n!/r!o r!apenas cancela o último r de n
então 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;
}