北京企业建网站定制价格,简单建设网站首页,wordpress 瀑布流分页,开网站制作公司实现代码#xff1a;C
实现方法#xff1a;通过递推法、递归法、矩阵快速幂方法 适用#xff1a; 范围小且单次查询时#xff0c;可以不用记忆化处理。 范围大或多次查询时#xff0c;应使用记忆化处理。 时间复杂度#xff1a;
递归法#xff1a;O(n^2)--递推法(…实现代码C
实现方法通过递推法、递归法、矩阵快速幂方法 适用 范围小且单次查询时可以不用记忆化处理。 范围大或多次查询时应使用记忆化处理。 时间复杂度
递归法O(n^2)--递推法(动态规划)O(n)--矩阵快速幂O(nlgn)--斐波那契数列公式O(1) 目录
递推法
递推法记忆化
递归法
递归法记忆化
矩阵快速幂方法 斐波那契通项公式 递推法
#includebits/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;
}
递推法记忆化
#includebits/stdc.h
using namespace std;
vectorintf;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 iostreamusing namespace std;int fn(int n){//递归出口1if(n0)return 0;//递归出口2else if(n1 )return 1;elsereturn fn(n-1)fn(n-2); }int main(){int n; int ans;cinn;ansfn(n);coutansendl;}
递归法记忆化
#includebits/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.husing namespace std;typedef unsigned long long ull;const int mod1e97;class Matrix//矩阵类
{
public:int row,col;//row为矩阵的行数,col为矩阵的列数 ull matrix[5][5];//矩阵 Matrix(int r2,int c2,int tag0)//构造函数 {rowr;colc;memset(matrix,0,sizeof(matrix));if(tag)//若传入tag为非0,则初始化为单位矩阵 {for(int i0;imin(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 i0;im1.row;i)//遍历第一个矩阵的每一行 {for(int j0;jm2.col;j)//遍历第二个矩阵的每一列 {for(int k0;km1.col;k)//第一个矩阵的行与第二个矩阵的列一一对应相乘再相加 {ull tmpm1.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(power1){ansans*m;power--;}powerpower1;mm*m;}return ans;
}ull F(Matrix M,ull n)//计算N阶斐波那契数列
{Matrix ansmatrix_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;cinT;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;cinN;coutF(M,N)endl;}return 0;
} 斐波那契通项公式
