-2

我正在尝试计算帕斯卡三角形第 100 行中的特定条目是否可被 3 整除。我使用公式 nCr 计算，其中 n=100 和 r 是第 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 之类的值，我得到了包含十进制和 e 的大数字。我在互联网上搜索发现实际上有 12 个数字不能被 3 整除，但我的程序在第 100 行给了我 63 个不能被 3 整除的数字，这是错误的。谁能告诉我我是什么做错了。

4

2 回答 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结构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 回答
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乘以4的倍数！可整除 1 次

所以10！(6! * 4!) 可以被 3 整除。实际上是 3 * 70。

于 2012-03-09T20:13:57.040 回答