6

わかりました、最初に、ユーザー入力に基づいてシリーズからフィボナッチ数を返す簡単なコードを書きました..

n=5 は 3.. を生成します。

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

シリーズから値を返すだけでなく、シリーズの合計を返すようにコードを変更することを考えていましたが、合計を実行しようとしているときに、return ステートメントに誤って 1 を追加し、驚いたことに、合計が正しく返されました。

以下のコードは、n=5 に対して 7 を返します。

これが合計を計算する正しい方法かどうかはわかりません...

1を追加すると、シリーズの合計がどのように機能するかまだわかりません。誰か説明してもらえますか??

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

編集：

フィボナッチ数列の場合..0,1,1,2,3,5,8,13,21,34,55,89,144....

私はいくつかのランダムな n を試しました

n=13

関数は 376 を返します

0+1+1+2+3+5+8+13+21+34+55+89+144 = 376

n=10

関数は 88 を返します。

0+1+1+2+3+5+8+13+21+34=88

4

6 に答える 6

10

プログラムへの変更fibonacciは、実際に合計を計算するために機能します。ただし、再帰を使用した方法は非効率的です。これに対処する 1 つの方法は、2 回目の再帰呼び出しで再利用できるように、計算された値がキャッシュされる「動的プログラミング」アプローチを使用することです。ただし、n 番目のフィボナッチ数は基数から順方向に計算できます。これを再帰的に実装すると、次のようになります。

public static int fib_r (int a, int b, int n) {
    if (n == 1) return a;
    if (n == 2) return b;
    return fib_r(b, a+b, n-1);
}

public static int fib (int n) {
    return fib_r(0, 1, (n > 0) ? n : 1);
}

合計に対応するコードは次のようになります。

public static int sumfib_r (int a, int b, int n) {
    if (n == 1) return a;
    if (n == 2) return b;
    return sumfib_r(b, a+b+1, n-1);
}

public static int sumfib (int n) {
    return sumfib_r(0, 1, (n > 0) ? n : 1);
}

末尾再帰は、コンパイラ/インタプリタによって末尾呼び出し削除の一部として単純なループに変更されることがよくあります。

あなたは尋ねました：

1を追加すると、シリーズの合計がどのように機能するかまだわかりません。誰か説明してもらえますか??

この質問は、実際にはアルゴリズムを理解することに関するものであり、SO で話題になっていると思います。ただし、アルゴリズムが機能する理由を説明するには数学が必要です。ですから、これは本当に数学の問題です。フィボナッチ数の和に関するよく知られた定理があります。F[i]が i 番目のフィボナッチ数でありS[n]、 が最初のフィボナッチ数の合計である場合n、上記の定理は次のように述べています。

    S[n] = F[n+2] - 1

したがって、 の定義から考えるとS[n+2]、

S[n+2] = S[n+1] + F[n+2]

S[n] + 1次に、次のように置き換えF[n+2]ます。

S[n+2] = S[n+1] + S[n] + 1

認識する必要があるのは、「add 1 modified」fibonacci関数です。

以下は、元の回答で提供した合計をプログラムが計算することの帰納法による証明です。Fあなたのfibonacci関数をS表し、あなたの「変更された1つの追加」関数を表しましょうfibonacci。

F[1] = 0
F[2] = 1
F[i] = F[i-1] + F[i-2] for i > 1

S[1] = 0
S[2] = 1
S[i] = S[i-1] + S[i-2] + 1 for i > 1

次に、次の証明が必要ですk > 0。

         k
       .---  
S[k] =  >   F[i]
       `---
       i = 1

上記の合計は、次の場合にのみ真となることに注意してください。

S[1] = F[1]
S[k] = F[k] + S[k-1] for k > 1

証明はかなり簡単です。基本的なケースは自明です。

S[1] = F[1] = 0
S[2] = F[2] + F[1] = 1
S[3] = S[2] + S[1] + 1 = F[3] + F[2] + F[1] = 2

誘導ステップは次k > 2のとおりS[j+1] = F[j+1] + S[j]です。0 < j < k+1j = k+1S[k+2] = F[k+2] + S[k+1]

    S[k+2] = S[k+1] + S[k] + 1
=>  S[k+2] = (F[k+1] + S[k]) + (F[k] + S[k-1]) + 1
=>  S[k+2] = (F[k+1] + F[k]) + (S[k] + S[k-1] + 1)
=>  S[k+2] = F[k+2] + S[k+1]

これで証明が完了する.

于 2013-03-13T20:13:06.613 に答える
3

いいえ、そうではありません。コードの 2 番目のバージョンは、指定された値までのフィボナッチ関数のすべての値の合計を計算しません。そして、ベースケースも間違っています!

合計を再帰的に計算する場合は、次のように問題を 2 つの部分に分割します。

public static int fib(int n) {
    return n < 2 ? n : fib(n-1) + fib(n-2);
}

public static int sumfib(int n) {
    return n < 0 ? 0 : fib(n) + sumfib(n-1);
}

最初の関数はフィボナッチを計算し、2 番目の関数は指定された数値まで値を加算します。

于 2013-03-13T19:50:41.700 に答える
0

あなたのコードはテストする必要がn<1あります - 0以下の引数を渡すと、それは永遠に続きます...

それ以外 - を呼び出すとfib(5)、次のようになります。

...
return(fib(4) + fib(3))

fib(4):
return(fib(3) + fib(2))

fib(3):
return(fib(2) + fib(1))

now fib(2) == 1 by your definition, and fib(1) == 0

so fib(3) == 1

then fib(4) == 1 + 1 = 2

and fib(5) = fib(4) + fib(3) = 2 + 1 = 3

Now if you add the '+1', the following happens:

fib(1) and fib(2) are unchanged
fib(3) = 1 + 0 + 1 = 2
fib(4) = fib(3) + fib(2) + 1 = 4
fib(5) = fib(4) + fib(3) + 1 = 4 + 2 + 1 = 7

元の方法は良いですが、フィボナッチ数の「順序」をどのように考えるかによって異なります (最初の数をどうしたいか)。

于 2013-03-13T19:53:09.890 に答える
0

再帰的にフィボナッチ数を計算する方法は非常に非効率的です。数値 43 の後、答えが得られるまで 30 秒以上かかります。52 という数を計算するのにどれくらいの時間がかかるか調べてみたところ、約 47 分かかりました。そのため、時間は非常に速く成長します。

再帰コード:

private int calculateRecursivelyInt(int fnum)
    {
        if (fnum == 0)
            return 0;
        if (fnum == 1)
            return 1;

        return calculateRecursivelyInt(fnum - 1) + calculateRecursivelyInt(fnum - 2);
    }

ループははるかに効率的です

    //This method will be able to calculate till the F46 because int can't hold a 
    // bigger number. You can calculate till 92 with a type long and till 93 with
    // unsigned long in C#.

    private int calculateLoopInt(int num)
    {
        int fnum = 0;
        int val1 = 0;
        int val2 = 1;

        for (int i = 0; i < num; i++)
        {
            if (num == 1)
                fnum = 1;
            else if (i > 0)
            {
                fnum = val1 + val2;
                val1 = val2;
                val2 = fnum;
            }
        }
        return fnum;
    }
于 2013-10-19T22:27:14.757 に答える