計算大数の組み合わせ

Question

パスカルの三角形の100番目の行の特定のエントリが3で割り切れるかどうかを計算しようとしています。これはnCrのnCrを使って計算しています。 100行目のエントリ。 私は組み合わせ

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などの値のために、私はそれで小数や電子を含む多数を取得しています。 インターネットで検索したところ、実際には3で割り切れない12の数字がありますが、私のプログラムは100行目で3で割り切れない63の数字を与えています。これは間違っています。私は間違っている。

Answer 1

「nCr」はn-choose-rの省略形であると仮定します。

nCrが3で割り切れるかどうかを調べるには、結果を計算する必要はなく、3で割り切れるかどうかを調べるだけです。 3で割り切れ、何回r！ 3で割り切れ、何回（n-r）！です。

これは本当に簡単です - 1！ 3,2で割り切れない！そうじゃない、3！一度割り切れる。 4！ 5！一度割り切れる。 6！ 2回割り切れるし、7もそうだ！ 8！ 9！ 4倍に割り切れるようになります。すべての方法をnまで進めてください（または、段階的に計算することなく数式を計算してください。それほど難しいことではありません）。

明確化 - 私の数学の研究では、ヘブライ語で "何度nが3で割り切れるか"が適切な英語の方法ではないかもしれません。 「n！3 m回割り切れる」とは、kが3で割り切れない場合はn!=3^m*kを意味します。

EDIT：例。 10c4が3で割り切れるかどうかを見てみましょう。

何回かkを何回か言ってみましょう！ （！divisiblity列を計算する際のk列だけのデモンストレーションのために、あなたが実際にそれを必要としない場合）3で割り切れる：

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で割り切れないものを意味する）、 6！ 2倍に割り切れます。 4！ 1回に割り切れる。

だから10！ （6！* 4！）は3で割り切れます。実際には3 * 70です。

Answer 2

まず第一にあなたはダブルスを使用していますが、私はそれは良い考えではないと思います。浮動小数点数はしばらくするとエラーになります。

数は、巨大な1は、以下の方法を使用できることが成長しない場合：しかし、これはまだ十分ではありません。この場合、

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 1とディビジョンとの乗算をインターリーブする必要がないことを主張することができ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がかなり大きい場合、データの操作に（バイト数の配列として表現されるため）時間がかかることになります。それを小さく保つことで、長い計算時間を避けることができます。