求斐波那契数列(全部求法)
全部 数列 那契
2023-09-11 14:19:53 时间
功能
用函数实现求斐波那契数列
文章目录
方法一:递归(适合n<=130,不求余)
已优化为带有记忆性的递归,时间复杂度为n,n>130时f(n)会爆long long
long long f[1005]={0,1,1};
long long Fib(int n)
{
if(f[n]!=0) return f[n];
return f[n]=dp(n-1)+dp(n-2);
}
cout<<Fib(n)<<endl;
方法二:数组打表(适合n<=1e7,求余)
时间复杂度也为n,求余可使n达到10 ^ 7,也可不求余,同递归
const long long mod=1e9+7;
#define M 1000005
long long f[M]={0,1};
void Fib()
{
for(int i=2;i<=M;i++)
f[i]=(f[i-1]+f[i-2])%mod;
}
Fib();
cout<<f[n]<<endl;
方法三:矩阵快速幂(适合n<=10^18,求余)
时间为很小的log n,能达到的n最大,唯一缺点是模板麻烦
#include <memory.h>
#define ll long long
const ll mod=1e9+7;
const int N=4;
ll tmp[N][N];
void mul(ll a[][N],ll b[][N],ll n)
{
memset(tmp,0,sizeof(tmp));
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
for(int k=0;k<n;k++)
tmp[i][j]=(tmp[i][j]+a[i][k]*b[k][j])%mod; //这里求余
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
a[i][j]=tmp[i][j];
}
ll res[N][N];
void Pow(ll a[][N],ll k)
{
memset(res,0,sizeof(res));
for(int i=0;i<N;i++)
res[i][i]=1;
while(k){
if(k&1)
mul(res,a,N);
mul(a,a,N);
k>>=1;
}
}
ll Fib(ll n)
{
ll vis[N][N]={{1,1},{1,0}};
Pow(vis,n);
return res[0][1];
}
cout<<Fib(n)<<endl;
矩阵快速幂求斐波那契数列样板题:Fibonacci
因为小数不能求余,通项公式实现基本没有任何优势,所以以上方法大概是极限了
相关文章
- 工作总结 1 sql写法 insert into select from 2 vs中 obj文件和bin文件 3 npoi 模板copy CopySheet 最好先全部Copy完后 再根据生成sheet写数据 4 sheet.CopyRow(rowsindex, rowsindex + x); 5 npoi 复制模板如果出现单元格显示问题
- JavaScript - math.js 数学库,实现 math.add() “数字累加“ 计算总和的操作(例如:循环 N 个整数或小数,然后再循环内 “+=“ 叠加算数)适用于Vue等全部前端项目
- 面试复盘 常见面试题 正则表达式 验证邮箱 Java 1-100万整数全部随机生成不重复 遍历一个文件夹下所有的文件和子文件 数据库查询班级最高分 创建一个学生表,记录学生父母名字
- 购物车全部数据,带商品信息
- 游戏开发者必备的 10 大工具:释放游戏开发的全部潜力
- js字符串中查看有没有在数组中的值有的话全部替换掉
- Win10大丰收的节奏 微软收编iOS全部150万应用
- 【生产问题】:邮件无法查看全部、甚至整个邮件都没了(表数据无法查询全部,否则一直卡查询状态)
- FineReport: 参数为空选出全部值(按条件查询,空条件时直接过滤,不进行查询。。)