斐波那契数列的六种解法

大家好，我是讯享网，很高兴认识大家。

做这个问题之前,我们需要了解到斐波那契数列是什么东西?是干什么的?

斐波那契数列是什么?

一、斐波那契数列指的是这样一个数列：1、1、2、3、5、8、13、21、…… 这个数列从第三项开始，每一项都等于前两项之和。

二、应用：通常在个别股票中不是太准确，通常在指数上有用。当市场行情处于重要关键变盘时间区域时，这些数字可以确定具体的变盘时间。使用斐波那契数列时可以由市场中某个重要的阶段变盘点向未来市场推算，到达时间时市场发生方向变化的概率较大。

接下来我就跟大家讲讲用C++的6种算法解斐波那契数列!

第一种解法(递归法):

利用C++求解斐波那契数列第N项数字是什么?我们可以用C++算法,递归法来进行表示.我们知道,斐波那契数列的每一项数字都等于前面两项数字之和,那么用计算机函数来表示,若fun为求斐波那契数列的第N项的函数,那么fun(N)=fun(N-1)+fun(N-2).

而且我们知道,斐波那契数列数列的第一项和第二项都为1,但是我们在算fun(2)的时候,需要fun(1)+fun(0).第一项数字为1是肯定的,那第0项数字呢?我们就将它姑且当作为0,也可以解决这个问题!

C++递归法求斐波那契数列:

#include<bits/stdc++.h> //万能头文件 using namespace std; //批准使用std int fun(int n){ //递归函数,求斐波那契数列的第N项数字  if(n==0) //如果是第0项数字  return 0; //返回0  if(n==1) //如果求第一项数字  return 1; //返回1  return fun(n-1)+fun(n-2); //进行递归式调用 }int main(){ //主函数  while(1){ //无限循环输入  int n; //定义整数,代表斐波那契数列的第n项数字  cin>>n; //输入n  cout<<fun(n)<<endl; //输出斐波那契数列的第n项数字的值  } return 0; //结束 }

讯享网

第一种解法的效率(时间复杂度):

fun(n)=

fun(n-1)= fun(n-2)=

fun(n-1-1)= fun(n-1-2)= fun(n-2-1)= fun(n-2-2)=

.........................................................................................................................

fun(2)= ............................................

fun(1)=1 fun(0)=0 .................................................

最后得出结论,第一种解法普通递归法的时间复杂度为O(2^n).时间复杂度实在是太大了,虽然这样写代码很简短,比其他两种算法都短,但是由于时间效率太慢,不建议使用!

第二种解法(记忆化递归/动态规划):

第一种普通递归法为什么那么的慢呢?那是因为它重复计算了很多个以前早就已经计算过的值,相当于重复计算,所以时间非常的慢.我们要怎么优化呢?当然是避免重复运算了!怎么避免呢?自然是将我们计算过的值存下来,第二次还需要这个值的时候不需要计算了,直接把之前存下来的那个值返回回去就可以了!

我们刚开始,需要进行初始化,就是将这个记录所有需要计算的值的这个数组初始化(第i个下标的值代表斐波那契数列的第i项数字的值),初始化为-1!为什么呢?这样体现了做标记的作用,代表这个下标所存的斐波那契数列的第i项数字的值还没有算过.这样在递归过程中,如果是-1,代表没有算过,进行赋值,如果算过来,不需要递归重复计算了,直接将这个的值返回回去就可以了!

因为我们知道斐波那契数列的第一项和第二项是什么,所以在最开始就要进行赋值f[0]=0(第0项自然为0)f[1]=1;f[2]=1;然后就可以进行递归了!

这种算法既可以称为"记忆化递归"(毕竟将算过的东西存起来,就是记录下来了),它还有一个名字,是一种很通用的算法"动态规划"!

C++记忆化递归/动态规划求斐波那契数列:

讯享网#include<bits/stdc++.h> //万能头文件 using namespace std; //允许使用std里面的函数及类 long long f[]; //记忆化的数组 long long fun(int n){ //求斐波那契数列的第n项数字  if(n==0) //如果是第0项  return 0; //返回值为0  if(n==1) //如果求第一项  return 1; //那么返回值为1  if(f[n]==-1) //如果这个值没有计算过  f[n]=fun(n-1)+fun(n-2); //进行递归存储计算  return f[n]; //计算过的话就直接返回 }int main(){ //主函数  memset(f,-1,sizeof(f)); //将f这个数组里面的每一个值赋值为-1  f[0]=0; //将第0项赋值为0  f[1]=1; //将第1项赋值为1  f[2]=1; //将第2项赋值为1  while(1){ //无限循环输入  int n; //定义整数,代表斐波那契数列的第n项数字  cin>>n; //输入n  cout<<fun(n)<<endl; //利用记忆化递归/动态规划算法函数求斐波那契数列的第n项数字的值  } return 0; //结束 }

第二种解法的效率(时间复杂度):

将每一个所计算出来的值记录下来,时间复杂度为O(N^2).已经算是非常快的了!虽说代码比之前的普通递归法要复杂了很多,但是已经快了很多倍了!

第三种解法(递推):

我们在第二种解法中已经看到,可以将值存起来进行计算,不过第二种方法是自上而下来进行计算,和第一种普通递归一样,不过省略了重复的计算步骤.

而我们第三种解法,是自下而上计算:

我们都知道,第一个数为1,第二个数也为1,可以存入数组f里面,那么f[3]是不是等于f[1]+f[2]=2了呢?算出了f[3],f[4]就等于f[2]+f[3]=3了!

这样自下而上计算非常的简洁迅速,快到了极点,堪称斐波那契数列最快的算法之一了.

C++递推解法:

#include<bits/stdc++.h> //万能头文件 using namespace std; //允许使用std里面的函数及类 long long f[]; //记忆化的数组int main(){ //主函数  long long n; //定义整数,代表斐波那契数列的第n项数字  f[1]=f[2]=1; //将斐波那契数列的第一项和第二项初始化为1  cin>>n; //输入n  for(long long i=3;i<=n;i++) //从第三项开始自下而上计算  f[i]=f[i-2]+f[i-1]; //f[i-2]和f[i-1]的值绝对是算出来了的  cout<<f[n]<<endl;// 输出数组下标为n的值  return 0; //结束 }

第三种解法的效率(时间复杂度):

快,非常快,快到无与伦比!只有O(N)的时间复杂度(无论斐波那契数列的多少项,都可以很快算出来,当然要配上一个高精度),而且代码是如此的简短!

第四种解法(滚动递推法):

这个算法是在斐波那契数列的递推法进行优化，因为我们是求斐波那契数列的第n项，第n项只等于n-1项+n-2项，所以我们可以优化空间，我们的f不用开的那么大，只需要开到3就可以了，我们求第i项的时候，可以利用%运算进行存储。

C++滚动递推法：

讯享网#include<bits/stdc++.h> //万能头文件 using namespace std; //允许使用std里面的函数及类 long long f[]; //记忆化的数组int main(){ //主函数  long long n; //定义整数,代表斐波那契数列的第n项数字  f[1]=f[2]=1; //将斐波那契数列的第一项和第二项初始化为1  cin>>n; //输入n  for(long long i=3;i<=n;i++) //从第三项开始自下而上计算       f[i%3]=f[(i-2)%3]+f[(i-1)%3]; //这样子，我们可以用散列表的思想进行空间优化 cout<<f[n]<<endl;// 输出数组下标为n的值  return 0; //结束 }

第四种解法的效率（空间复杂度）

时间复杂度的效率和第三种算法递推法是一样的，我们进行了空间优化，本来是O()的空间复杂度被降到了O(3)的空间复杂度，你看这是不是非常的节省空间。

第五种解法（三个变量循环法）

因为我们上述4种解法都应用到了算法，带偏了大家的思想。其实我们只需要定义三个变量a,b,c依次循环迭代赋值即可。

C++三个变量循环法代码：

#include<bits/stdc++.h> //万能头文件 using namespace std; //批准使用std int main(){ //主函数   int n; //定义 cin>>n; //输入 int a, b,c; //定义 c=a=b=1; //初始化 for (int i=3;i<=n;i++){ //循环      c=b+a;//等于前两项的和      a=b; //赋值 b=c; //赋值 } cout<<c<<endl; //输出 return 0; //结束}

第五种解法的效率(时间复杂度和空间复杂度):

其实我们只需要一个简单的循环就可以解决这个问题，根本不需要上述四种算法，时间复杂度和空间复杂度与第四种解法滚动递推法一样，非常的快。

讯享网

第六种解法（矩阵快速幂法）

对与斐波那契数列，我们可以进行拆分，经过细腻的拆分过后，形成了以下的方程式（其中N>=1，如何实现求 f(N)）：

[f(N+1) f(N) ]

[ f(N) f(N-1) ]

等于-->

[1 1]^n

[1 0]

我们可以使用快速幂法,先跟大家讲一讲快速幂是什么？

快速幂算法是用来快速计算指数表达式的值的，例如 ,普通的计算方法 2*2*2*2…乘次，如果一个数字的计算都要计算那么多次的话，那么这个程序一定是失败的。

学完快速幂之后就可以用几十次计算求出答案了

快速幂思想其实很简单，就是公式的转换
1、当指数是偶数时，我们可以让指数除以2，底数乘以底数
2、当指数是奇数时，我们可以将指数变为奇数

例如 210

指数是偶数，210 = 45

指数是奇数，45 = 4 * 44

指数是偶数， 4 * 44 = 4 * 162

指数是偶数，4 * 162 = 4 * 2561

指数是奇数， 4 * 2561=4 * 256 * 2560

指数为0时停止，那么答案就是计算 4 * 256 = 1024

我们知道了快速幂是什么，就可以对上述的矩阵进行快速幂的拆分了。

[1 1]^n

[1 0]

( [1 1]^N/2 )^2

( [1 0] )

比如原N为8，需要进行32次相乘运算，可以变为:

x^2^2^2

三次运算即可完成，时间复杂度变为O(logN)。当然，由于N不等于2的整数次幂的情况比如 9 ，可以变成 8 + 1 相乘的形式，

x^2^2^2*x

所以时间复杂度会稍微变大一点点。

C++矩阵快速幂法代码：

讯享网#include<bits/stdc++.h> using namespace std; struct Matrix{ int row,column; int v; Matrix(){ memset(v,0,sizeof(v)); } }; Matrix multiply(Matrix a,Matrix b){ Matrix ans; ans.row=a.row; ans.column=b.column; for(int i=1;i<=a.row;i++) { for(int j=1;j<=b.column;j++) for(int k=1;k<=a.column;k++) ans.v[i][j]+=a.v[i][k]*b.v[k][j]; } return ans; } Matrix power(Matrix a, long long n){ Matrix ans,base; ans.v[1][1]=ans.v[2][2]=1; while(n!=0){ if(n%2==1) ans=multiply(ans,base); base=multiply(base,base); n/=2; } return ans; } int main(){ long long n; cin>>n; Matrix ans, base ,last; base.row=2; base.column=2; base.v[1][1]=base.v[1][2]=base.v[2][1]=1; last.row=2; last.column=1; last.v[1][1]=last.v[2][1]=1; if(n==1||n==2) cout<<1<<endl; else{ ans=power(base,n-2); ans=multiply(ans,last); cout<<ans.v[1][1]<<endl; } return 0; }

总结：

有些时候，一个问题，能用简单算法解决就尽量不要用复杂的算法，例如斐波那契数列，如果复杂度O（n）可以解决，可以直接用三个变量循环法解决，不必要用复杂的递归递推算法了。

如果O（n）都不能解决，那就只能使用矩阵快速幂法了！