-2

パスカルの三角形の100行目の特定のエントリが3で割り切れるかどうかを計算しようとしています。これは、n =100でrが100行目の異なるエントリである式nCrを使用して計算しています。以下のコードを使用して組み合わせを計算しています

 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個の数字が間違っています。間違ったこと。

4

2 に答える 2

1

「nCr」はn-choose-rの省略形だと思いますか、それともNからrを選択しますか？

nCrが3で割り切れるかどうかを確認するには、結果を計算する必要はありません。3で割り切れるかどうかを判断するだけです。nの回数を確認する必要があります。は3で割り切れる、そして何回r！は3で割り切れ、何回（nr）！は。

それは本当に簡単です-1！3、2で割り切れません！そうではない、3！一度割り切れる。4！と5！また、一度分割可能です。6！は2回除算可能であり、7も同様です。と8!。9！は4回除算可能です。nまで行き（または段階的に計算せずに数式を計算します。それほど難しいことではありません）、確認します。

明確化-私の数学はヘブライ語で研究しているので、「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で除算できないもの）、6！2 x 4で割り切れる！1回割り切れる

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

于 2012-03-09T20:13:57.040 に答える
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構造体を使用できます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が非常に大きい場合、データの操作には時間がかかります（数値はバイト数の配列として表されるため）。小さく保つことで、計算時間が長くなるのを防ぐことができます。

于 2012-03-09T20:26:56.730 に答える