1

ちょっとしたコードがあり、その繰り返し関係を書く必要があります。このコードは単純に 2 の n 乗を計算します。どんな助けでも大歓迎です。

public static int two(int n) {

     if (n==0) {
       return 1;
     } else if (n%2 == 0) {
       int x = two(n/2);
       return x*x;
     } else { 
       return 2 * two(n-1)
}
4

2 に答える 2

1

関数の定式化はほぼ漸化式です。基本的に、必要なのは変数の変更を実行することだけなのでtwo、再帰の引数は ですn。たとえば、次のフィボナッチ関数を使用します。

public static int fib(n) {
    if (n==0) {
        return 1;
    } else if (n==1) {
        return 1;
    } else {
        return fib(n-1) + fib(n-2);
    }
}

その実装は恐ろしく非効率的であるため、使用したくないでしょうが、再帰関係を簡単に記述できます。

フィブ0 =1
fib 1 =1
fib n+2 = fib n+1 + fib n

フィボナッチの例では、実際に変数を変更する必要はありません。ただし、two関数を使用すると、リレーションを簡単に記述できます。

于 2010-09-20T01:29:11.580 に答える
0

再帰呼び出しを持たない行は、c と呼ぶ一定の時間内に実行されます。

T(n)=T(n-1)+c if n is odd.
T(n)=T(n/2)+c if n is even.

n が奇数の各再帰呼び出しの後、次の再帰呼び出しでは n-1 が偶数になります。したがって、最悪の場合、n 奇数で開始します -> n-1 は偶数です -> (n-1)/2 は奇数です -> (n-1)/2-1 は偶数です...

たとえば、n=19 で開始すると、19 は奇数 -> 18 は偶数 -> 9 は奇数 -> 8 は偶数 -> 4 は偶数 -> 2 は偶数 -> 0 となります。

再帰ツリーの深さは約 lgn で、各レベルに c 個の操作があるため、実行時間は clgn=O(lgn) です。

于 2012-07-18T13:32:06.490 に答える