斐波那契数列 优化矩阵求法实例
在做编程题目的时候经常会遇到“斐波那契数列”相关的题目,尤其在做OJ中。下面说一些方法:
(一)递归
递归是最慢的会发生重复计算,时间复杂度成指数级。
long long fac(int n)
{
if(n==1) return 1;
else if(n==2) return 2;
else return fac(n-1)+fac(n-2);
}
(二)循环
利用临时变量来保存中间的计算过程,加快运算。
long long fac(int n)
{
long long a=1,b=2,c;
if(n==1) return 1;
else if(n==2) return 2;
else
{
for(int i=3;i<=n;i++)
{
c=a+b; a=b; b=c;
}
}
return b;
}
(三)矩阵乘法+空间换时间(减少乘法,取模运算)
数列的递推公式为:f(1)=1,f(2)=2,f(n)=f(n-1)+f(n-2)(n>=3)
用矩阵表示为:
进一步,可以得出直接推导公式:
由于矩阵乘法满足结合律,在程序中可以事先给定矩阵的64,32,16,8,4,2,1次方,加快程序的执行时间。(有些题目需要取模运算,也可以事先进行一下)。给定的矩阵次幂,与二进制有关是因为,如下的公式存在解,满足Xi={0或1}:
为了保证解满足 Xi={0或1},对上述公式的求解从右向左,即求解顺序为Xn,Xn-1,Xn-2,....,X1,X0。
完整代码实现如下:
///求解fac(n)%100000,其中n为大于等于3的正整数
#include<stdio.h>
#include<math.h>
long long fac_tmp[6][4]={ ///存放矩阵次幂
///位置:00 01 10 11
{24578,78309,78309,46269}, ///32次幂%100000
{1597,987,987,610}, ///16次幂%100000
{34,21,21,13}, ///8次幂%100000
{5,3,3,2}, ///4次幂%100000
{2,1,1,1}, ///2次幂%100000
{1,1,1,0}, ///1次幂%100000
};
void fac(int);
int main()
{
int n;
scanf("%d",&n);
fac(n);
return 1;
}
void fac(int k) ///k>=3
{
int i;
long long t00=1,t01=1,t10=1,t11=0; ///表示矩阵的1次幂
long long a,b,c,d;
k=k-3; ///公式中是n-2次幂,(t00,t01,t10,t11)表示1次幂。所以一共减3次
for(i=k;i>=32;i=i-32) ///对于大于等于32的k;
{
a=(t00*fac_tmp[0][0]+t01*fac_tmp[0][2])%100000;
b=(t00*fac_tmp[0][1]+t01*fac_tmp[0][3])%100000;
c=(t10*fac_tmp[0][0]+t11*fac_tmp[0][2])%100000;
d=(t10*fac_tmp[0][1]+t11*fac_tmp[0][3])%100000;
t00=a; t01=b; t10=c;t11=d;
}
i=4;
while(i>=0) ///对于小于32的k(16,8,4,2,1);
{
if(k>=(long long)pow(2,i)) ///如果k大于某一个2的次幂
{
a=(t00*fac_tmp[5-i][0]+t01*fac_tmp[5-i][2])%100000; ///(5-i):矩阵的2的i次幂在数组fac_tmp中的位置为fac_tmp[5-i]
b=(t00*fac_tmp[5-i][1]+t01*fac_tmp[5-i][3])%100000;
c=(t10*fac_tmp[5-i][0]+t11*fac_tmp[5-i][2])%100000;
d=(t10*fac_tmp[5-i][1]+t11*fac_tmp[5-i][3])%100000;
t00=a; t01=b; t10=c;t11=d;
k=k-(int)pow(2,i);
}
i--;
}
a=(t00*2+t01*1)%100000;
printf("%lld\n",a);
}
相关文章
- 这篇文章主要介绍了C#实现斐波那契数列的几种方法整理,主要介绍了递归,循环,公式和矩阵法等,小编觉得挺不错的,现在分享给大家,也给大家做个参考。一起跟随小编过来看看吧...2020-06-25
- 斐波那契数列来源于兔子繁殖问题,所以也叫兔子序列,下面这篇文章主要给大家介绍了关于JavaScript输出斐波那契数列的实现方法,需要的朋友可以参考下...2021-06-27
- 以下是对C++中输出斐波那契数列的两种实现方法进行了详细的介绍,需要的朋友可以过来参考下,希望对大家有所帮助...2020-04-25
- 这篇文章主要介绍了C语言数据结构递归之斐波那契数列的相关资料,希望通过本文能帮助到大家,让大家理解掌握这部分内容,需要的朋友可以参考下...2020-04-25
- 斐波那契数列 优化矩阵求法实例,需要的朋友可以参考一下...2020-04-25
- 本篇文章是对递归形式与非递归形式的斐波那契数列的用法进行了详细的分析介绍,需要的朋友参考下...2020-04-25
- 这篇文章主要介绍了c++输出斐波那契数列示例,需要的朋友可以参考下...2020-04-25
c#斐波那契数列(Fibonacci)(递归,非递归)实现代码
c#斐波那契数列(Fibonacci)(递归,非递归)实现代码,需要的朋友可以参考一下...2020-06-25- 本篇文章是对求斐波那契(Fibonacci)数列通项的七种实现方法进行了详细的分析介绍,需要的朋友参考下...2020-04-25
- 本篇文章介绍了,基于使用递归推算指定位数的斐波那契数列值的解决方法。需要的朋友参考下...2020-06-25
- 下面小编就为大家带来一篇C语言实现斐波那契数列(非递归)的实例讲解。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧...2020-04-25