用BigInteger計算C（n，r）的StackOverflowError

我實現了遞歸算法來計算N選擇r。 C（n，r）= C（n-1，r-1）+ C（n-1，r）。我想計算C（100000，50000），這是拋出stackoverflow。感謝任何幫助。用BigInteger計算C（n，r）的StackOverflowError

錯誤：

java Solution 1 1 10000 5000 Exception in thread "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) at java.lang.StringBuilder.toString(StringBuilder.java:430) at Solution.findNcr(Solution.java:31) at 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 
    } 
}

來源

2012-10-28 NaveenBabuE

每次遞歸算法可以被轉換爲迭代形式，反之亦然，所以你只需要找出如何使用for和while來編寫它 – ignis

是的，我想出了一種方法，但是這需要創建一個尺寸爲N * R的二維數組，我的要求N <= 100000000，所以我會佔用空間大小爲100000000 * 50000000（最壞的情況）。因此，我繼續使用這種自頂向下的方法和一個哈希映射緩存，我應該嘗試迭代方法和se它如何執行。謝謝！ – NaveenBabuE

你做那麼什麼是你得到了什麼。每次遞歸調用都會將調用者狀態保存在堆棧中，並且由於您正在計算C（100000,50000），這將導致數百萬次遞歸調用最終導致所有堆棧空間耗盡。你可能想看看像我這裏提到的更好的算法Write a faster combinatorics algorithm

來源

2012-10-28 17:23:14 FUD

感謝您的輸入。我不願意實現可以進行乘法和除法的算法，因爲它們很昂貴。所以，我採用了這種動態編程方法。我會嘗試你的算法。 – NaveenBabuE

你可以嘗試增加你的堆棧大小。

對您的JVM使用-Xss。

我想1 GB應該爲你做的伎倆。您可以計算它以獲得更準確的價值。

來源

2012-10-28 17:33:56

感謝您的回覆。我正在嘗試找出一種解決方案，它可以儘可能少地使用空間並且運行得更快。 – NaveenBabuE

它是否必須是遞歸算法？ –

不一定是遞歸算法！ – NaveenBabuE

這個簡單的實現運行時間爲10秒100000 | 50000

（真正使用你應該添加一些檢查和不同的方法，當r < N - R（只爲週期會有不同的bounderies ......沒有根本的改變）

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-28 19:36:21

+1我冒昧地通過避免創建字符串來提高代碼的效率。 –

用BigInteger計算C（n，r）的StackOverflowError

回答

相關問題