3

我实现了递归算法来计算 N 选择 r。C(n,r) = C(n-1,r-1) + C(n-1,r)。我想计算 C(100000, 50000)，它抛出了 stackoverflow。感谢任何帮助。

错误：

java 解决方案 1 1 1 10000 5000 线程“main”中的异常 java.lang.StackOverflowError at java.lang.System.arraycopy(Native Method) at java.util.Arrays.copyOfRange(Arrays.java:3210) at java.lang.String .(String.java:215) 在 java.lang.StringBuilder.toString(StringBuilder.java:430) 在 Solution.findNcr(Solution.java:31) 在 Solution.findNcr(Solution.java:35)

代码：

private static HashMap<String,BigInteger> hm =
    new HashMap<String,BigInteger>(10000000,0.9f); 
private static BigInteger findNcr(int n, int r) {
    BigInteger topLVal = BigInteger.valueOf(0);
    BigInteger topRVal = BigInteger.valueOf(0);
    int parentN = 0, parentR = 0;

    if( r >= n-r)  //ncr = nc(n-r)
       r = n-r;

    if (r == 0 || r == n)
        return BigInteger.valueOf(1L);
    else if (r == 1 || r == n-1)
        return BigInteger.valueOf(n);
    else if (hm.containsKey(""+n+""+r)) { //line 31
        return hm.get(""+n+""+r);
    } else{
        parentN = n-1; parentR = r-1;
        topLVal = findNcr(parentN, parentR);
        topRVal = findNcr(parentN, r);
        hm.put(""+parentN+""+parentR,topLVal);
        hm.put(""+parentN+""+r, topRVal);
        return topLVal.add(topRVal);      //line 35
    }
}
4

3 回答 3

3

好吧，你所做的就是你得到的。您进行的每个递归调用都会将调用者状态保存在堆栈中，并且由于您正在计算 C(100000, 50000) 这将进行数百万次递归调用，因此最终会耗尽所有堆栈空间。你可能想研究一个更好的算法，就像我在这里提到的写一个更快的组合算法

于 2012-10-28T17:23:14.790 回答
1

您可以尝试增加堆栈大小。

对您的 JVM 使用 -Xss。

我想 1 GB 应该可以为您解决问题。您可以计算它以获得更准确的值。

于 2012-10-28T17:33:56.647 回答
1

这个简单的实现对于 100000 运行长达 10 秒 | 50000。

（对于实际使用，当 r < n - r 时，您应该添加一些检查和不同的方法。（只是循环会有不同的边界......不是根本性的变化）

private static BigInteger ncr(int n, int r) {
    BigInteger top = BigInteger.ONE;
    BigInteger bot = BigInteger.ONE;

    for(int i = n; i > r; --i){
        top = top.multiply(BigInteger.valueOf(i));
    }

    for(int i = r; i > 1; --i){
        bot = bot.multiply(BigInteger.valueOf(i));
    }

    return top.divide(bot);
}
于 2012-10-28T19:36:21.533 回答