3

我要计算nCr modulo 142857。以下是我的 Java 代码：

private static int nCr2(int n, int r) {
    if (n == r || r == 0) {
        return 1;
    }
    double l = 1;
    if (n - r < r) {
        r = n - r;
    }
    for (int i = 0; i < r; i++) {
        l *= (n - i);
        l /= (i + 1);
    }
    return (int) (l % 142857);
}

这会及时给出 nCr O(r)。我想要一个算法在比这更短的时间内得到结果。有这样的算法吗？

4

3 回答 3

1

由于您的数字不是素数，因此此答案不适用。但是您可以轻松地将 142857 分解为素数，计算相应的模数，然后使用中国剩余定理得到您的结果。这对于您正在使用的数字可能有意义，也可能没有意义。

在任何情况下，您都必须避免加倍，除非您可以确定所有中间结果都可以仅用 53 位精确表示（否则您会失去精度并得到无意义的结果）。

于 2013-11-07T09:05:28.947 回答
1

您可以预先计算给定n和r对的结果，并将它们硬编码在表中int t[][]。

稍后，在运行时，当您需要时nCr(n, r)，您只需查找此表：t[n][r]。

这是O(1)在运行时。

于 2013-11-06T17:41:18.897 回答
0

您已经在您提到的功能中获得了大部分答案。如果 n 是固定的，而 r 是可变的，则可以使用 nCr = nC(r-1) * (n - r + 1) / r。因此，您可以为 nCr 使用表并以增量方式构建它（与其他答案提到的预计算不是增量的不同）。

因此，您的新函数可以通过传递表进行递归。

于 2013-11-06T20:20:17.507 回答