Java 用双整数计算 C(n,k) 和阶乘

Question

我想计算C(n,k)的答案，例如C(10,2)=10*9/2*1 = 45 如果我用像 10 这样的小数字测试我的代码，代码就可以工作。但是，当我尝试计算 C(1000,900) 时，它会编译

Exception in thread "main" java.lang.ArithmeticException: / by zero

我看到有人说应该使用BigInteger，但是我试了之后还是有错误。

例如：我把int factorial改成BigInteger factorial，而 cSelect 中的 for 循环，我无法将 int i 更改为 BigInteger 类型，结果，答案 up/factorial(y) 有错误。

请帮我解决这个问题。谢谢！！

public class Test {

    // Write a factorial function
    static int factorial(int m) {
        int result =1;
        for (int i=2; i<=m; i++) {
            result = result*i;
        }
        return result;
    }

    // Caculate C(x,y)
    static int cSelect(int x, int y) {
        int up=1;
        for(int i=x; i>=(x-y+1); i--) {
            up = up*i;
        }
        return up/factorial(y);
    }

    public static void main(String[] args) {
        System.out.println(cSelect(1000,900));

    }

}

Answer 1

您的代码很容易翻译成 factorial。从 ONE 开始，为循环中的每个 i 乘以 BigInteger.valueOf(long)。喜欢，

// Write a factorial function
static BigInteger factorial(int m) {
    BigInteger result = BigInteger.ONE;
    for (int i = 2; i <= m; i++) {
        result = result.multiply(BigInteger.valueOf(i));
    }
    return result;
}

您的其他函数完全相同，加上除以factorial(y)的结果。喜欢，

// Caculate C(x,y)
static BigInteger cSelect(int x, int y) {
    BigInteger up = BigInteger.ONE;
    for (int i = x; i >= (x - y + 1); i--) {
        up = up.multiply(BigInteger.valueOf(i));
    }
    return up.divide(factorial(y));
}

没有其他改变我得到

63850511926305130236698511142022274281262900693853331776286816221524376994750901948920974351797699894319420811933446197797592213357065053890

我认为是正确的。

Answer 2

您必须使用 BigInteger 进行计算。

您尝试计算的值约为 6.385051192630516e+139，它不能表示为 Java 原始整数值。

即使结果是可表示的，您得到被零除错误的原因是除数表达式 900! ∗ 100! 溢出为零。然后除以那个零。

它溢出为零的原因是它可以被2^32和2^64整除。这可以通过使用一些简单的代数来计算 900 中 2 的因数个数来证明！和 100！

Answer 3

首先，return 的值必须是 BigInteger，因为 C(1000,900) 的结果远远超出 int.

的范围

其次，您不需要单独的 factorial() 方法。在迭代时进行除法将通过不创建过大的中间值来改善内存占用（以进行多次除法为代价，但即便如此它实际上可能更快）。

像这样：

static BigInteger cSelect(int x, int y) {
    BigInteger v = BigInteger.ONE;
    for (int i = x, j = 1; j <= y; i--, j++)
        v = v.multiply(BigInteger.valueOf(i)).divide(BigInteger.valueOf(j));
    return v;
}

向下数i向上数j，除法永远不会有分数。

测试

System.out.println(cSelect(10, 2));
System.out.println(cSelect(1000, 900));

输出

45
63850511926305130236698511142022274281262900693853331776286816221524376994750901948920974351797699894319420811933446197797592213357065053890

Java 用双整数计算 C(n,k) 和阶乘

Java Compute C(n,k) and factorial with biginteger

java

biginteger

factorial