0

フィボナッチ数を返す単純な再帰アルゴリズムがあります。

private static double fib_recursive(int n){
    if(n <= 2) return 1;
    else return fib_recursive(n-1) + fib_recursive(n-2);
}

ここでのタスクは、このメソッドが特定のコンピューターで400 番目のフィボナッチ数を計算するのにかかる時間を返すことです (例: fib_recursive(400))。このメソッドが答えを出すのに時間がかかるため、関数を実行できないため、「Would」は太字になっています。

どうすればそれを最もよく達成できますか？

4

3 に答える 3

3

各再帰呼び出しを実行する時間を計算し、再帰呼び出しの数を計算すると、答えが得られます。

よりスマートな再帰アルゴリズムを使用してこれを行うより高速な方法がありますが、アルゴリズムにはタイミング情報を入力するだけです。

于 2010-09-20T19:27:09.733 に答える
1

タイミングは、測定したいものの前後System.currenTimeMillis()の差を取ることによって行われます。System.nanoTime()

于 2010-09-20T19:55:21.500 に答える
0

私はおそらく最善の解決策ではありませんでしたが、ここに私が持っているものがあります(将来誰かを助けるかもしれません):

1) 再帰的な方法で 42 番目の (たとえば) フィボナッチ数を計算するのに必要な時間を測定しました。

2) 反復法を使用して、再帰法で 42 番目のフィボナッチ数を計算しながら実行されるプログラムの行数を数えました。(行 = 3*fib_iterative(42)-2)

3) 2 を 1 で割ると、1 ミリ秒で実行される行の平均数が得られました。

4) 反復法を使用して、400 番目のフィボナッチ数を再帰法で計算しながら、実行されるプログラムの行数を数えました。(行 = 3*fib_iterative(400)-2)

5) 4 を 3 で割ると、fib_recursive(400) が費やした推定時間が得られました。

// Recursive algorithm, calculates Fibonacci number (slow)
private static double fib_recursive(int n){
    if( n <= 2) return 1;
    else return fib_recursive(n-1) + fib_recursive(n-2);
}

// Iterative algorithm, calculates Fibonacci number (fast)
private static double fib_iterative(int n){
    double a = 1, b = 1;
    for (int i = 2; i <= n; i++){
        b = a + b;
        a = b - a;
    }
    return a;
}

// Get time, which fib_recursive(int) needs to calculate the 400th Fibonacci number
private static long testRecursiveFor400(){
    int elapsedTime = 0;
    int start = (int) System.currentTimeMillis();
    fib_recursive(42);
    elapsedTime = (int) (System.currentTimeMillis() - start);
    return (3 * (long) fib_iterative(400) - 2) / ((3 * (int) fib_iterative(42) - 2) / elapsedTime);
}
于 2010-09-20T22:11:54.423 に答える