斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、……在数学上，斐波纳契数列以如下被以递归的方法定义：

F（0）=0，（n = 0）

F（1）=1，（n = 1）

F（n）=F(n-1)+F(n-2)（n≥2，n∈N*）


斐波那契数列指的是这样一个数列 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987，1597，2584，4181，6765，10946，17711，28657，46368

特别指出：第0项是0，第1项是第一个1。

这个数列从第2项开始，每一项都等于前两项之和。

现实生活中，运用斐波那契数列的例子很多，而且这也是面试中经常会考到的经典问题

那么，这么一个看似不好想象的规律用代码怎么实现呢？


这里有几种方法：

递归实现：
<时间复杂度O（2^N）>

#include<iostream>usingnamespacestd;longlongFibonacci1(longlongn)//用longlong类型考虑到大数问题{if(n<2){returnn;}else{returnFIB(n-1)+FIB(n-2);}}intmain(){cout<<Fibonacci1(5)<<endl;//求某一项的值system("pause");return0;}

递归似乎看起来很简单明了，若给的项数n较大时，其效率较低。


2.非递归实现：

<时间复杂度O（N）>

longlongFibonacci2(intn){longlong*fibArray=newlonglong[n+1];//根据项数n开辟数组fibArray[0]=0;fibArray[1]=1;//手动设置好前两个数，由此可以求得下一个数的值for(inti=2;i<=n;++i){fibArray[i]=fibArray[i-1]+fibArray[i-2];//当前数等于前两个数加和}longlongret=fibArray[n];delete[]fibArray;returnret;}

非递归效率相对递归较高，但是两者意义相同。

这两种方法，都需要掌握。

下面将两种方法整合一起：

#include<iostream>usingnamespacestd;longlongfibonacci_1(intn)//递归{if(n<2){returnn;}returnfibonacci_1(n-1)+fibonacci_1(n-2);}voidfibonacci_2(intn)//非递归{inti;longlong*fibArray=newlonglong[n+1];fibArray[0]=0;fibArray[1]=1;for(i=2;i<n;i++)fibArray[i]=fibArray[i-1]+fibArray[i-2];for(i=0;i<n;i++)cout<<fibArray[i]<<"";}intmain(void){inti,n,k;printf("请输入斐波那契数列项数：");cin>>n;printf("请选择：1.递归2.非递归：");cin>>k;if(k==1)for(i=0;i<n;i++)cout<<fibonacci_1(i)<<"";elsefibonacci_2(n);system("pause");return0;}

若有纰漏，欢迎指正。