我想计算 fib(n) 被调用 FOR EACH n 的次数。我写的代码如下:
#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]);
}
}
我已经尝试打印数组 count[] 来获得结果,除了 count[0] 之外,结果类似于斐波那契数列:
count[0] = 34 count[1] = 55 count[2] = 34 count[3] = 21 count[4] = 13 count[5] = 8 count[6] = 5 count[7] = 3 count[8] = 2 count[9] = 1 count[10] = 1
有没有办法从数学上显示这个结果,也许是递归公式?另外,为什么 count[0] 或者 fib(0) 不延续斐波那契数列? 谢谢。
最佳答案
因为 count[1]
将针对每个 count[2] + count[3]
调用,但 count[0]
只会为 count[2]
调用...count[1]
没有贡献,因为它是一个终点。
关于数学公式:
if n == 0: fib(N - 1)
else: fib(N-(n-1))
关于c++ - 计算 fib(n) 被调用 FOR EACH n 的次数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/41149449/