0

私はJAVAを自分で学んでいて、今はメモ化について学んでいます。でもなんか道に迷ってる…

再帰を使用し、メモ化を使用してアルゴリズムを高速化することにより、Java で組み合わせを計算する方法についてのサンプル コードはありますか?

C5,3 = 5*4*3/3*2*1 = 10 を計算する方法のように? しかし、再帰を使用していますか？

4

2 に答える 2

1

例でそれをやってみましょう20選択5

20 choose 5として定義されているので 20! / ( 5! * (20-5)! )

これらの階乗計算を格納するために使用できるmemoizationため、再帰の下で継続的に再計算する必要はありません。

それで：

    //STORING FACTORIAL COMPUTATIONS
    private Map<Integer,Long> factorialMap = new HashMap<Integer,Long>();


    public Long getFactorial(int number) {

        //CHECK IF I ALREADY COMPUTED THIS FACTORIAL
        Long val = factorialMap.get(number);
        if(val != null) {
            //GOT IT!
            return val;
        } else {
            //NEED TO COMPUTE!
            val = getFactorialRecursive(number);
            //STORING IT TO SAVE COMPUTATION FOR LATER
            factorialMap.put(number, val);
            return val;
        }
    }

    //RECURSIVE FUNCTION TO COMPUTE FACTORIAL
    public Long getFactorialRecursive(int number) {
        if(number < 2) {
            return 1L;
        } else {
            return number * getFactorialRecursive(number-1);
        }
    }


    //ACTUAL CALL TO "20 choose 5"
    public Long combination(int fromVal, int chooseVal) {
        return getFactorial(fromVal)/(getFactorial(chooseVal)*getFactorial(fromVal-chooseVal));
    }
于 2012-10-06T22:12:35.113 に答える
0

combinatoricslibここで無料で利用できるライブラリを使用できます。

http://code.google.com/p/combinatoricslib/

于 2012-10-06T21:50:40.263 に答える