Obliczanie liczby razy fib (n) nazywa się DLA KAŻDEGO n - c ++, c, rekursja, fibonacci

Chcę obliczyć, ile razy fib (n) nazywa się FOR EACH n. Napisałem kod jak poniżej:

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

Próbowałem wydrukować liczbę tablic [], aby uzyskać wynik, gdzie wynik jest podobny do liczb fibonacciego, z wyjątkiem liczby [0]:

liczba [0] = 34 liczba [1] = 55 liczba [2] = 34 liczba [3] = 21 liczba [4] = 13 liczba [5] = 8 liczba [6] = 5 liczba [7] = 3 liczba [8] = 2 liczba [9] = 1 liczba [10] = 1

Czy istnieje sposób matematycznego pokazania tego wyniku, może formuły rekurencyjnej? Ponadto, dlaczego nie liczy [0], a raczej fib (0), czy nie kontynuuje sekwencji fibonacci? Dzięki.

Odpowiedzi:

Bo count[1] zostanie wezwany dla każdego count[2] + count[3] ale count[0] będzie tylko wezwany count[2]...count[1] nie przyczynia się, ponieważ jest końcem.

Jeśli chodzi o wzór matematyczny:

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

Co do obliczeń

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

Mam nadzieję, że to wyjaśni.

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