2232: 绪论-斐波那契数列1-递归方法
金币值：2
定数：7
时间限制：1.000 s
内存限制：128 M
正确：123
提交：197
正确率：62.44% 命题人：
题目描述
斐波那契数列（$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(2^n)$。