0

繰り返しますが、私はまだ再帰を扱っています。基本ケースの 1 つに関して質問があります。

UPD: a と b はシーケンスの最初の数字を表し、n は計算される合計の目的の位置です。

私のコードは次のとおりです。

public static int fib(int a, int b, int n) {

    if (n <=1) { 
        return a;
    } else if (n == 2) {
        return b;
    } else {
        return (fib(a, b, n - 1) + fib(a, b, n - 2));
    }
}

2 行目では、手動でプログラムをトレースする前に、「n<=0」のままにしました。ただし、プログラムをトレースして実行すると、差分の回答が得られました。問題は、ある時点で n will = to 1 でした。そのため、最初の基本ケースを n<=1 に変更し、同じ答えを得ました。

ここで問題は、メソッドを次のように呼び出したとします: fib(2,3,6) 答えは = 21 (with line 2 = " n<=1") であるはずですが、行 2 が "n<=0" の場合答えは27でした。

行 2 で "n<=0" が与えられた場合、最終的に n = 1 の場合、プログラムに何が起こるか知りたい

4

4 に答える 4

1

n が 1 の場合の呼び出しは、n が 0 で n が -1 の 2 つの追加の再帰呼び出しを生成します。これらの 2 つの再帰呼び出しはa、正解に 2 回追加されます。

于 2013-10-16T05:46:51.870 に答える
0

n 番目のフィボナッチを取得するには、n を関数に渡すだけです。

シーケンスが 0、1、1、2、3 であると仮定すると...

あなたのアルゴリズムは

if n = 1 return 0
else if n = 2 return 1
else return fib(n - 2) + fib(n - 1)
于 2013-10-16T05:40:34.283 に答える
0

両方が最終的にヒットし、正しい n を返す代わりに、渡された変更されていない変数aまたはのいずれかを返す 2 つの基本ケースがありますb。

あなたのコードは、フィボナッチ数列を計算する 2 つの異なる方法の乱雑な組み合わせです。非常に非効率的な再帰的なものがあります：

public static int fib(int n) {
    if (n <=1)
        return n;

    return fib(n-1) + fib(n-2);
}

しかし、ご覧のとおり、すべての厳しい時間を計算します。シーケンスが表示されている場合は、2 つの数値 a と b を引数として最初から繰り返すことができます。

a 0 1 1 2 3 5 ...
b 1 1 2 3 5 8 ...

次の a を計算するには、b を使用します。新しい a を計算するには、a と b を加算します。したがって、より効率的なアルゴリズムは次のとおりです。

public static int fib(int a, int b, int n) {
    if (n <= 0)
        return a;

    return fib(b, a+b, n-1);
}

Java は末尾呼び出しの最適化を行わないため、末尾呼び出しを最適化する他の言語と同様に再帰は機能しません。したがって、次のような非再帰バージョンの方が適しています。

public static int fib(int n) {
    for(int a=0, b=1;; n--) {
        if (n <= 0)
           return a;
        int tmpa = a;
        a = b;
        b += tmpa;
    }
}
于 2013-10-16T08:43:52.470 に答える
0

私は実際に自分の質問に答えました。

ある時点で n = 3 になっていることがわかります。したがって、返される値は最終的に次のように n =1 になります。

return (Fib(2,3,2)+ Fib(2,3,1))

n = 1 になったので、2 行目の基本ケースは適切に実行されます。

一方、行 2 の基本ケースが「n<=0」の場合、n =3 の場合

return (Fib(2,3,2) + Fib(2,3,1))

次に、 Fib(2,3,1) によりメソッドが再度呼び出され、結果は n =0 になり、n = -1 & n =-2になり、答えが異なります。

//UpDATED: n =0 & n=-1 を持つと、答えが異なります

于 2013-10-16T05:49:12.623 に答える