4

n!/(n-r)!r!C#で計算する必要があります。階乗関数を使って小さな数を計算するのは簡単ですが、数が 100 のように大きくなるとうまくいきません。より大きな数の組み合わせを計算できる他の方法はありますか?

4

4 に答える 4

17

まず、二項係数を計算しようとしていることに注意してください。

計算方法はいくつかあります。BigInteger を使用する場合、オーバーフローを心配する必要はありません。

方法 1: 階乗を使用します。

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

方法 2: 再帰を使用します。

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

ただし、この方法は、結果をメモしない限り高速ではありません。

方法 3: 乗算の数を最小限に抑え、早期に除算することについて、より賢明になります。これにより、数値が小さく保たれます。

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、可能であれば数値を小さく保ちます。

于 2012-03-08T15:49:40.573 に答える
5

エリックが言ったことに従って、早期に分割することは大いに役立ちます。このようにして、最終結果が 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;
}
于 2012-10-16T10:55:58.767 に答える
0

.net 4.0以降では、int/longの代わりにクラスBigIntegerを使用します

他の.netの場合は、たとえばIntXのカスタムビッグナンバークラスを使用します：http：//www.codeplex.com/IntX/

于 2012-03-08T15:33:39.453 に答える