多数のための組み合わせを計算する

Question

Pascalの三角形の100行目の特定のエントリが3列目で特定のエントリが3またはNOTで割り切れるかどうかを計算しようとしています。。 以下のコードを使用して組み合わせを計算しています

 public static double Combination(int n, int m, double comb)
    {
        for (int r = -1; ++r < m; )
            comb = comb * (n - r) / (r + 1);
        return comb;
    }

.

しかし100C16のような値の場合、私はそれに10進数とEを含む大きな番号を得る。 私はインターネットを検索しましたが、実際には3で割り切れない12の番号があることがわかりましたが、私のプログラムは私に間違っている100行で3分割されていない63個の数字を与えます。間違っています。

Answer 1

私は "NCR"がN-SELECT-Rの省略形であると仮定するか、nからrのrを選択します。

NCRが3つずつ分割可能なかどうかを確認するには、結果を計算する必要はありません。あなたはそれが3で割り切れられているかどうかを理解する必要があるだけです3で分割されています、そしてそれから何回r！ 3で割れ目があり、数回（n-r）！ です

それは本当に単純です - 1！ 3,2で割り切れない！じゃない、3！一度分割されています。 4！ 5！一度も分割されています。 6！分割可能な2回、そうです。 8！ 9！分割可能な4回などです。 nまでずっとn（段階的に計算せずに数式を作動させる、それだけではありません）、そしてチェックしてください。

明確化 - ヘブライ語の中のMath Studies、SO "N！が3つずつ分割されています。 「N！は3 M倍に分けられる」とは、n!=3^m*kがあることを意味します。ここで、Kはまったく3で割り切れません。

編集：例。 10C4が3で割り切れるかどうか見てみましょう。

kを何回言っているかを言ってみましょう。 3で割れ目があります（K！列はデモンストレーションのためだけに、実際には配置列を計算するときは必要ありません）：

  k      k!     Divisibility
  1       1     0
  2       2     0
  3       6     1
  4      24     1
  5     120     1
  6     720     2
  7    5040     2
  8   40320     2
  9  362880     4
 10 3628800     4

.

10c4は10です！ /（6！* 4！）。

10！分割可能な4回（意味10！= 3 ^ 4 * 3×3） 6！ 3回分別されています 4！割り切れる1回です

SO 10！ （6！* 4！）は3で割れ目です。実際には3 * 70。

Answer 2

最初のあなたはダブルスを使っています、私はそれが良い考えだとは思わない。浮動小数点数はしばらくの後にエラーを与えます。

数が大きくなると、巨大な方式では以下の方法を使用できない場合：

public static long nCr (int m, int n) {
    long tmp = 1;
    int j = 2;
    int k = m-n;
    for(int i = m; i > k; i--) {
        tmp *= i;
        while(j <= n && tmp%j == 0) {
            tmp /= j++;
        }
    }
    while(j <= n) {
        tmp /= j++;
    }
    return tmp;
}

.

この場合はこれはまだ十分ではありません。その場合、BigInteger のSystem.Numerics構造体を使用できます。

public static BigInteger nCr (int m, int n) {
        BigInteger tmp = 1;
        int j = 2;
        int k = m-n;
        for(int i = m; i > k; i--) {
            tmp *= i;
            while(j <= n && tmp%j == 0) {
                tmp /= j++;
            }
        }
        while(j <= n) {
            tmp /= j++;
        }
        return tmp;
    }

.

BigIntegerが除去と乗算を相互に扱う必要がないと主張することができます。ただし、BigIntegerが非常に大きい場合は、データに対する操作が時間がかかります（番号は数のバイトの配列として表されます）。それを小さく保つことによって長い計算時間を避けることができます。