算法编程：计算斐波那契数列

实现代码：C++

实现方法：通过递推法、递归法、矩阵快速幂方法

适用：

范围小且单次查询时，可以不用记忆化处理。

范围大或多次查询时，应使用记忆化处理。

时间复杂度：

递归法：O(n^2)-->递推法(动态规划)：O(n)-->矩阵快速幂：O(nlgn)-->斐波那契数列公式：O(1)

递推法：

递推法+记忆化：

递归法：

递归法+记忆化：

矩阵快速幂方法：

斐波那契通项公式：

递推法：

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	int x = 0;
	int y = 1;
	int ans;
	
	cin >> n;
	if(n == 0)ans = 0;
	
	else if(n = 1)ans = 1;
	else {
		for(int i = 2;i <= n;++ i)
		{
			ans = x + y;
			x = y;
			y = ans;
		}
	}
	
	cout << ans << endl;
	return 0;
}

递推法+记忆化：

#include<bits/stdc++.h>
using namespace std;
vector<int>f;


int main()
{
	int n;
	cin >> n;
	f.push_back(0);
	f.push_back(1);
	for(int i = 2;i <= n;++ i)
	{
		f.push_back(f[i-1]+f[i-2]);
	}
	for(int i = 1;i <= n;++ i)
	{
		cout << f[i] << endl;
	}
	return 0;
}

递归法：


  #include <iostream>
  using namespace std;
  
	  int fn(int n)
  {
	  //递归出口1
	  if(n==0)
	  return 0;
  
  //递归出口2
	  else if(n==1 )
	  return 1;
  
	  else
	  return fn(n-1)+fn(n-2); 
  }
  
  
  int main()
  {
	  
	  int n; 
	  int ans;
  
	  cin>>n;
  
	  ans=fn(n);
  
	  cout<<ans<<endl;
  }

递归法+记忆化：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll p = 1e9 + 7;
const int inf = 1e9,N = 1e5 + 3;
ll dp[N];

ll f(int n)
{
	if(n <= 2)return 1;
	if(dp[n] != -1)return dp[n];
	
	return dp[n] = (f(n - 1) + f(n - 2)) % p;
}


int main()
{
	memset(dp,-1,sizeof dp);
	int n;cin >> n;
	cout << f(n) << endl;
	
	return 0;
}

矩阵快速幂方法：

//计算斐波那契数列有很多种方法,而当阶数N很大时,矩阵快速幂算法是最佳的 
#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ull;

const int mod=1e9+7;

class Matrix//矩阵类 
{
public:
	int row,col;//row为矩阵的行数,col为矩阵的列数 
	ull matrix[5][5];//矩阵 
	Matrix(int r=2,int c=2,int tag=0)//构造函数 
	{
		row=r;
		col=c;
		memset(matrix,0,sizeof(matrix));
		if(tag)//若传入tag为非0,则初始化为单位矩阵 
		{
			for(int i=0;i<min(r,c);i++)
			{
				matrix[i][i]=1;//对角线元素初始化为1 
			}    
		}    
	}        
};

Matrix operator *(Matrix m1,Matrix m2)//矩阵乘法,返回结果矩阵 
{
	Matrix ans;//构造一个2行2列的矩阵,初始化均为0 
	memset(ans.matrix,0,sizeof(ans.matrix));
	for(int i=0;i<m1.row;i++)//遍历第一个矩阵的每一行 
	{
		for(int j=0;j<m2.col;j++)//遍历第二个矩阵的每一列 
		{
			for(int k=0;k<m1.col;k++)//第一个矩阵的行与第二个矩阵的列一一对应相乘再相加 
			{
				ull tmp=m1.matrix[i][k]*m2.matrix[k][j]%mod; 
				ans.matrix[i][j]=(ans.matrix[i][j]+tmp)%mod;
			}
		}
	}
	return ans;
}

Matrix matrix_mul(Matrix m,ull power)//矩阵快速幂,求解矩阵m的power次幂 
//原理与普通快速幂相同,重载了矩阵相乘的函数之后可直接套用普通快速幂算法 
{
	Matrix ans(2,2,1);//初始化为单位矩阵 
	while(power)
	{    
		if(power&1)
		{
			ans=ans*m;
			power--;
		}
		power=power>>1;
		m=m*m;
	}
	return ans;
}

ull F(Matrix M,ull n)//计算N阶斐波那契数列 
{
	Matrix ans=matrix_mul(M,n);//计算矩阵M的N次幂 
	return ans.matrix[1][0];//取其右下角元素即为最终答案 
}

int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int T;
	cin>>T;
	Matrix M(2,2,0);
	//构造一个矩阵为{ {1,1} , {1,0} } 
	//N阶斐波那契数列等于该矩阵的N次幂的右上角/左下角元素 
	M.matrix[0][0]=M.matrix[0][1]=1;
	M.matrix[1][0]=1;
	M.matrix[1][1]=0;
	while(T--)
	{
		ull N;
		cin>>N;
		cout<<F(M,N)<<endl;
	}
	return 0;
}