0

这些天我自己在学习java。该功能是计算组合。但是，我发现这个函数中 n 和 k 的数量有一个非常小的限制。每次如果我输入一个大的 n 或 k，例如 100，它就会给我

Exception in thread "main" java.lang.ArithmeticException: / by zero
at Combination.combination(Combination.java:29)
at Combination.main(Combination.java:47)

或者给我一个负数...

有没有办法让它适用于像 10000 这样的大数字？

谢谢！

import java.util.HashMap; import java.util.Map;

public class Combination {

private Map<Long,Long> factorialMap = new HashMap<Long,Long>();

public Long getFactorial(int number) {
    Long val = factorialMap.get(number);
    if(val != null) {
        return val;
    } else {
        val = getFactorialRecursive(number);
        factorialMap.put((long) number, val);
        return val;
    }
}

public Long getFactorialRecursive(int number) {
    if(number == 1 || number == 0) {
        return 1L;
    } else {
        return number * getFactorialRecursive(number-1);
    }
}

public Long combination(int fromVal, int chooseVal) {
    return getFactorial(fromVal)/(getFactorial(chooseVal)*getFactorial(fromVal-chooseVal));
}


public static void main(String[] args) {
    int   n, k;
    Combination comb = new Combination();
    java.util.Scanner console = new java.util.Scanner(System.in);

    while (true)  // will break with k > n or illegal k or n
    {  System.out.print ("Value for n:  ");
       n = console.nextInt();
       if ( n < 0 ) break;
       System.out.print ("Value for k:  ");
       k = console.nextInt();;
       if ( k > n || k < 0 )
          break;
       System.out.print(n +" choose " + k + " = ");
       System.out.println(comb.combination(n,k));
    }
    console.nextLine();    // Set up for "Press ENTER...


} }
4

2 回答 2

1

您应该使用该BigInteger对象：http ://docs.oracle.com/javase/7/docs/api/java/math/BigInteger.html

特别是你的问题是21！即使很长时间也太大，因此会溢出。另一种选择是使用双精度，但这会失去精度，所以如果你需要整数精度BigInteger是要走的路。

使用BigInteger您需要将整数转换为BigInteger：

BigInteger bi = new BigInteger(intVal+"");

然后使用add, multiply, divideand subtract（以及其他）来操纵您的值（例如）：

bi = bi.add(bi2);

然后您可以使用该方法longValue()取回该值（假设它适合很长）：

return bi.longValue();
于 2012-10-07T19:22:50.613 回答
1

我建议您考虑默认情况下Java不会递归超过大约10,000次，并且您不需要首先计算如此大的阶乘。

例如 1000!/999! 是 1000

如果您使用循环，您可以更早地停止。

public static BigInteger combination(int n, int r) {
    if (r * 2 > n) r = n - r;
    BigInteger num = BigInteger.ONE;
    BigInteger nr = BigInteger.valueOf(n - r);
    for (int i = n; i > r; i--) {
        num = num.multiply(BigInteger.valueOf(i));
        while (nr.compareTo(BigInteger.ONE) > 0 && num.mod(nr).equals(BigInteger.ZERO)) {
            num = num.divide(nr);
            nr = nr.subtract(BigInteger.ONE);
        }
    }
    while (nr.compareTo(BigInteger.ONE) > 0) {
        num = num.divide(nr);
        nr = nr.subtract(BigInteger.ONE);
    }
    return num;
}

Long顺便说一句，当我打算使用long效率较低时，我不会使用它。

为了比较，我使用 long 包含了相同的代码。

public static long combination2(int n, int r) {
    if (r * 2 > n) r = n - r;
    long num = 1;
    int nr = n - r;
    for (int i = n; i > r; i--) {
        num *= i;
        while (nr > 1 && num % nr == 0) {
            num /= nr--;
        }
    }
    while (nr > 1)
        num /= nr--;
    return num;
}
于 2012-10-07T19:34:57.787 回答