フィボナッチ数列 - 再帰総和は

Question

が[OK]を、私は最初に3を生成するユーザ入力に基づいて一連のフィボナッチ数を返すために、単純なコード..

N = 5 ..

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)); 
} 

EDIT：フィボナッチseries..0,1,1,2,3,5,8,13,21,34,55,89,144については

....

Iいくつかのランダムな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

Answer 1

あなたの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); 
} 

テール再帰がしばしばtail callの一部として、単純なループへのコンパイラ/インタプリタにより変更されるであろう除去。

あなたは尋ねた：

を私はまだシリーズの総和が、私は1を追加した場合、誰かが説明していただけますどのように動作するかを見つけ出すことができませんでした？

この質問は、実際に私が想定しているアルゴリズムを理解することです。しかし、アルゴリズムがなぜ機能するのかを記述するために数学が必要です。だから、これは本当に数学的な質問です。 well known theorem regarding the sum of Fibonacci numbersがあります。 F[i]場合は、i番目のフィボナッチ数で、S[n]は最初nフィボナッチ数の和である、その後、定理は、上記の状態：

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

をので、私たちが考える場合にS[n+2]の定義による

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

その後

、F[n+2]ためS[n] + 1を代入：

あなたがすべき

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

あなたの "変更1追加" fibonacci機能が認識されます。

---

以下は、私の元の解答で与えた合計をあなたのプログラムが計算するという誘導による証明です。 Fはあなたのfibonacci関数を表し、Sはあなたの「追加1修正」fibonacci関数を表します。上記の合計が真であることを

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

注意している場合にのみ場合：

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

証明はかなり単純です

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のための証拠を求めています。ベースケースは自明です。

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のためにことを考えると、0 < j < k+1ためS[j+1] = F[j+1] + S[j]、j = k+1場合には、等式が成立することを証明：S[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] 

これで完結しました。

Answer 2

いいえ、それはしませんを返します。コードの2番目のバージョンはではありません。は、指定された値までfibonacci関数のすべての値の合計を計算します。基本ケースも間違っています！このよう

あなたは再帰的に合計を計算したい場合は、二つの部分に問題を分割し、：

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); 
} 

最初の関数は、フィボナッチを計算し、第二は、与えられた数に値を加算するの面倒を見ます。

Answer 3

あなたのコードは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 

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

Answer 4

正しい方法は、accumlatorを使用することです。

コードが

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

Answer 5

が再帰的フィボナッチnumber.Afterにそれが取る数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; 
    } 

Answer 6

あります。

#include <iostream> 

// 0 1 1 2 3 5 8 13... 
// 

void fibb (int idx, int curr = 0, int next = 0) 
{ 
     std::cout << curr << ", "; 
     if(!idx) return; 
     if(curr == 0) { 
       curr = 1; 
       fibb(--idx, curr, next); 
       return; 
     } 
     next += curr; 
     fibb(--idx, next, curr); 
} 


int main() 
{ 
     fibb(10); 
}