fibonacci斐波那契数列详解 递归求Fn非递归求Fn求n最近的斐波那契数

斐波那契fibonacci

斐波那契额数列即前两项F(0)和F(1)都是1，之后的每一项都是前两项相加和即F(3)=2，F(4)=3，F(5)=5;

通项公式：F(n+2)=F(n+1)+F(n)。

1.递归求fn

给出一个n 求斐波那契数列的Fn

递归解法即写一个递归函数，注意两个点

1: 递归边界条件（n=0或者n=1）

2:递归式 F(n+2)=F(n+1)+F(n)

代码：

#include<cstdio>int F(int n){if(n==0||n==1) return 1;//递归边界else return F(n-1)+F(n-2);//递归式}int main(){int n;scanf("%d",&n);printf("%d\n",F(n));return 0 ;}

2.非递归求fn

因为递归虽然写起来非常方便，但是非常消耗空间，因此还需要掌握非递归算法，下图是递归算法之后的结果

那么，如何解决呢？

思路：用for循环

#include <cstdio>int main(){int n,Fn;scanf("%d",&n);int F1=1; //初始化int F2=1;for(n=n-2;n>0;n=n-2){F1=(F1+F2);F2=(F1+F2);}Fn=F1;if(n==0)//判断输出哪个位置上的数字Fn=F2;printf("%d\n",Fn);}

举个例子就能看懂了吧

就是用两个变量来循环相加。

3.求给出n最近的fibonacci数(冬季pat甲组第一题)

题目是给出一个n 求离这个n最近的斐波那契数，如果前后两个斐波那契数距离一样，输出较小的斐波那契数(这个斐波那契数列是从0、1开始的)

AC代码：

#include <cstdio>using namespace std;int main(){int a,b,c,n;scanf("%d",&n);a=0;b=1;while(c<=n){if(a+b-n>=n-c){break;}c=a+b;a=b;b=c;}printf("%d",c);}

这个代码虽然能跑AC，也是我自己写的。但是我还没完全理解。后续再更