斐波那契数列_详解（C语⾔）
⼀、斐波那契数列
斐波那契数列（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*）
定义
斐波那契数列指的是这样⼀个数列：
1,1,2,3,5,8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765,
10946, 17711, 28657, 46368 ……
这个数列从第3项开始，每⼀项都等于前两项之和。
⼆、算法
斐波那契数列的求法有递归求法和⾮递归求法，但通过以下对⽐可知，递归过程中产⽣很多了多余的计算，使得递归算法的时间复杂度很⼤，所以我们更常⽤⾮递归⽅法。
1.递归算法
代码
#include<stdio.h>
int fib(int n)
{
if(n==1||n==2)
return1;
else
return fib(n-1)+fib(n-2);
}
int main()
{
int n;
scanf("%d",&n);
printf("%d\n",fib(n));
return0;
}
2.⾮递归算法
代码
#include<stdio.h>
int main()
{明解c语言
int i,n,num[10];
num[1]=1;
num[2]=1;
for(i=3;i<=10;i++)
num[i]=num[i-1]+num[i-2]; scanf("%d",&n);
printf("%d",num[n]); return0;
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。