淘客建站程序,中小企业网站建设与管理主要讲授什么,智慧政务门户网站建设研究,免费的个人的网站文章目录求斐波那切数列的几个方法#xff1a;经典做法#xff1a;递推#xff1a;动态规划矩阵快速幂原理#xff1a;代码#xff1a;例题#xff1a;模拟过程求斐波那切数列的几个方法#xff1a;
经典做法#xff1a;
众所周知#xff1a;斐波那契数列的定义是f(…
文章目录求斐波那切数列的几个方法经典做法递推动态规划矩阵快速幂原理代码例题模拟过程求斐波那切数列的几个方法
经典做法
众所周知斐波那契数列的定义是f(n 1) f(n) f(n - 1) 我们有两种方式来实现一个是递归一个是动态规划
递推
int dfs(int n)
{if (n 1)return 1;if (n 2)return 2;return dfs01(n - 1) dfs01(n - 2);
}动态规划
int dfs03(int n)
{vec[maxn]vec[0] 1;vec[1] 2;int i;for (i 2; i n; i){vec[i] vec[i - 1] vec[i - 2];}return vec[i-1];
}矩阵快速幂
经典做法只要数一大就会超时我们可以用矩阵快速幂进行优化能将时间复杂度降到O(logN) 如果全位输出斐波那契数貌似最大能算法到93但是如果带mod那就可以算很大 常用于求第n位斐波那契数的后x位mod 10x
原理
快速幂矩阵 矩阵乘法左矩阵的第一行乘以右矩阵的第一列分别相乘乘完后相加 单位矩阵 nn的矩阵 mat ( i , i )1; 任何一个矩阵乘以单位矩阵就是它本身 n单位矩阵n 可以把单位矩阵等价为整数1。单位矩阵用在矩阵快速幂中 在斐波那契数列中 f[n ] 1 * f[n-1] 1 * f [n - 2] f[n-1] 1 * f[n-1] 0 * f [n - 2] 我们用矩阵来表示 这就表示了斐波那契数列如何用矩阵来实现。
代码
#include iostream
#include cstddef
#include cstring
#include vector
using namespace std;
typedef long long ll;
const int mod10000;
typedef vectorll vec;
typedef vectorvec mat;
mat mul(mat a,mat b)
{ mat c(a.size(),vec(b[0].size())); for(int i0; i2; i) { for(int j0; j2; j) { for(int k0; k2; k) { c[i][j]a[i][k]*b[k][j]; c[i][j]%mod; } } } return c;
}
mat pow(mat a,ll n)
{ mat res(a.size(),vec(a.size())); for(int i0; ia.size(); i) res[i][i]1;//单位矩阵 while(n) { if(n1) resmul(res,a); amul(a,a); n/2; } return res;
}
ll solve(ll n)
{ mat a(2,vec(2)); a[0][0]1; a[0][1]1; a[1][0]1; a[1][1]0; apow(a,n); return a[0][1];//也可以是a[1][0];
}
int main()
{ ll n; while(cinnn!-1) { coutsolve(n)endl; } return 0;
} #include bits/stdc.h
using namespace std;
typedef long long ll;
const ll mod1000000007;
struct matrix //定义结构体矩阵
{ll x[2][2];
} ;
matrix mul(matrix a,matrix b) //矩阵乘法运算
{matrix ans;memset(ans.x,0,sizeof(ans.x));for(int i0;i2;i) //三个循环表示两个方阵相乘可手动推写一遍{for(int j0;j2;j){for(int k0;k2;k){ans.x[i][j]a.x[i][k]*b.x[k][j];ans.x[i][j]%mod;}}}return ans;
}
matrix quickpow(matrix p,ll n) //矩阵快速幂与快速幂道理方法相同
{matrix ans;for(int i0;i2;i){for(int j0;j2;j){if(ij){ans.x[i][j]1;} //一开始初始化他为单位阵else ans.x[i][j]0;}}while(n)//快速幂{if(n1){ansmul(ans,p);}pmul(p,p);n1;}return ans;
}
int main()
{matrix m;m{0,1,1,1}; ll n;cinn;ll ans10;matrix ansquickpow(m,n-1);coutans.x[1][1]endl; return 0;
}
例题
POJ 3070
模拟过程
如果数很大比如求1000的斐波那契数列矩阵快速幂也求不出来,那咋办? 我们可以模拟斐波那契数列数列计算的过程斐波那契数列的定义是f(n 1) f(n) f(n - 1)我们可以手写加减模拟进行加减运算 例题 大菲波数 H DU - 1715
#include iostream
#include algorithm
#include string
#include map
#include set
#include vector
#include stack
#include queue
#include cstdio
#include cmath
#include cstdlib
#include cstring
using namespace std;
typedef long long ll;
int main(){int n,q,i,j,temp0;cinq;while(q--){cinn;char a[10010]1,b[10010]1,c[10010]{0};for(i0;in-2;i){int lenmax(strlen(a),strlen(b));for(j0;jlen;j){ //模拟加法temp0;if(a[j]0){ //短的数不加tempa[j]-0;}if(b[j]0){tempb[j]-0;}if(temp10){ //判断进位if(c[j]0){c[j]temp-10;}else{c[j]temp-100;}c[j1]10;}else{if(c[j]0){if(temp9){ //若前位进位了,而且加上的数字是9,那么还要进位!!!c[j]0;c[j1]1;}else{c[j]temp;}}else{c[j]temp0;}}}strcpy(a, b);strcpy(b, c);memset(c, 0, sizeof(c));}int lenstrlen(b);for(ilen-1;i0;i--){ //倒着输出printf(%c,b[i]);}printf(\n);}return 0;
}
