斐波那契数列的两种方法
斐波那契数列指的是这样一个数列 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项开始，每一项都等于前两项之和。
如果设F(n）为该数列的第n项（n∈N*），那么这句话可以写成如下形式:F(n)=F(n-1)+F(n-2)
显然这是一个线性递推数列。
下面来看看两种实现方法：
第一种，循环法来写：
# include<stdio.h>
int fibon(int n)
{
int f1=1;
int f2=1;
int f3=1;
{
for(int i=2;i<n;i++)
{
f3=f1+f2;
f1=f2;
f2=f3;
}
return f3;
}
}
int main()
{
for(int i=0;i<11;i++)
{
printf("%d\n",fibon(i));
}
}
int fibon(int n)
{
int f1=1;
int f2=1;
int f3=1;
{
for(int i=2;i<n;i++)
{
f3=f1+f2;
f1=f2;
f2=f3;
}
return f3;
}
}
int main()
{
for(int i=0;i<11;i++)
{
printf("%d\n",fibon(i));
}
}
结果是这样的
接下来用递推写，你会发现斐波那契真的太适合用递推公式来写了，炒鸡方便
# include<stdio.h>
int fibon(int n)
{
int fibon(int n)
{
if(n==0||n==1)
{
return 1;
}
else
return fibon(n-1)+fibon(n-2);
}
int main()
{
for(int i=0;i<11;i++)
{
printf("%d\n",fibon(i));
}
}
{
return 1;
}
else
return fibon(n-1)+fibon(n-2);
}
int main()
{
for(int i=0;i<11;i++)
{
printf("%d\n",fibon(i));
}
}
结果同样是这个
所以说用递推公式来写斐波那契数列真是简单很多，get到了吧！