fib（n）が呼び出された回数を計算する

Question

fib（n）がFOR EACH nと呼ばれる回数を計算したいと思います。

：私は結果が数[0]以外のフィボナッチ数に似ている結果を、取得するために[]カウント配列を印刷しようとしている

#include <stdio.h> 
#define N 10 

int count[N + 1]; // count[n] keeps track of the number of times each fib(n) is called 

int fib(int n) { 
    count[n]++; 

    if(n <= 1) 
     return n; 
    else 
     return fib(n - 1) + fib(n - 2); 
} 

int main() { 
    for(int i = 0; i <= N; i++) { 
     count[i] = 0; // initialize count to 0 
    } 
    fib(N); 

    // print values of count[] 
    for(int i = 0; i <= N; i++) { 
     printf("count[%d] = %d", i, count[i]); 
    } 
} 

：私は以下のようにコードを書かれています012カウント= [4] = 5カウント[5] = 8カウント[7] = 3カウント[0] = 34カウント[1] = 55カウント[2] = 34カウント[3] = 21カウント[4] = 13 カウント[5] [8] = 2カウント[9] = 1 カウント[10] = 1

ですがこの結果を数学的に示す方法は、おそらく再帰式ですか？また、なぜ[0]をカウントしない、あるいはfib（0）をフィボナッチシーケンスを継続しないのでしょうか？ありがとうございます。

Answer 1

それは末端だからcount[1]は、各count[2] + count[3]のために呼び出されることになるだろうが、count[0]のみcount[2]のために呼び出されることになるだろう... count[1]は寄与しないので。

数式について：計算のよう

if n == 0: fib(N - 1) 
else: fib(N-(n-1)) 

Answer 2

call(n)=call(n-1)+call(n-2)+1 
    call(1)=1 
    call(0)=1 

希望これは、物事を明確にします。

n | calls 
---+-------- 
0 | 1 
1 | 1 
2 | 3 
3 | 5 f(3)= f(2)[= f(1)+ f(0)]+ f(1) 
5 | 9 
. 
fib(n) 2*fib(n)-1