#include <iostream>
using namespace std;
int f(int n) {
if (n <= 1) return 1;
return f(n - 1) + f(n - 2);
}
int main() {
int a = 0;
for (int i = 1; i <= 5; i++) a += f(i);
cout << a << endl;
return 0;
}
- (1) 程序运行时输出的结果是______。（4 分）
- (2) 函数 f(n) 计算斐波那契第 n 项（f(1)=f(2)=1），写出 f(6) 的值______。（4 分）
- (3) 该程序的时间复杂度约为______。（5 分）
答案解析
（1）a = f(1)+…+f(5) = 1+2+3+5+8 = 19。（2）f(6) = 13。（3）朴素递归含大量重复计算，时间复杂度约 O(2ⁿ)（指数级），可用记忆化优化到 O(n)。