3

N choose r を計算する再帰アルゴリズムを実装しました。C(n,r) = C(n-1,r-1) + C(n-1,r)。stackoverflow をスローしている C(100000, 50000) を計算したかったのです。どんな助けにも感謝します。

エラー：

java Solution 1 1 10000 5000 スレッド「メイン」での例外 java.lang.String の java.lang.System.arraycopy(Native Method) の java.lang.StackOverflowError (Arrays.java:3210) .(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

スタックサイズを増やしてみてください。

-Xss を JVM に使用します。

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 に答える