2232: 绪论-斐波那契数列1-递归方法
金币值：2
定数：7
时间限制：1.000 s
内存限制：128 M
正确：38
提交：55
正确率：69.09% 命题人：
题目描述
斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以递推的方法定义：F(1)=1，F(2)=1, F(n)=F(n - 1)+F(n - 2)（n≥3，n∈N*）【注意：n小于等于20，可以使用递归实现，当n较大时不可以使用递归实现。例如，题目“斐波那契数列2-递推方法”就无法通过递归实现】
#include <stdio.h>
double fib(int n);
int main(void) {
int n;
scanf("%d",&n);
printf("fib(%d)=%.0lf",n,fib(n));
return 0;
}
/*提交以下代码*/
double fib(int n) {
}
输入格式
1行，第几项n
输出格式
见样例
输入样例 复制
5输出样例 复制
fib(5)=5提示
递归求解的时间复杂度比较高，是O(2N)。