斐波那契数列取模（大数）分治算法

斐波那契数列取模（大数）分治算法

这是算法课程上完分之策略后老师留的一道题目：

菲波那契数列如下：1,1,2,3,5,8,13,21,34......其中a[1] = 1, a[2] = 1, a[n]=a[n-1]+a[n-2]（n>=3）。对给定的下标n，求解a[n]%1997的值.

其中测试数据n是整数范围内。

这个题目，主要是用到很关键的一个数学知识，斐波那契数列的求法，可以转换为矩阵的连乘，矩阵的n此方算法又可以用分治的算法。

而且又有理论依据：(n*m)%c=[ (n%c)*(m%c) ]%c  ;   (n+m)%c=[   (n%c)+(m%c)  ]%c ,所以过程中的结果可以随时取模，而不影响最终的结果

关于斐波那契数列的矩阵连乘求法如下：

我们知道我们若要简单计算f(n)，有一种方法就是先保存 
a=f(0),b=f(1)，然后每次设： 
a'=b b'=a+b

并用新的a'和b'来继续这一运算

如果大家熟悉利用“矩阵”这一工具的话，就知道，如果把a、b写成一个向量[a,b]，完成上述操作相当于乘以矩阵 
0 1 
1 1 
也就是说，如果我们要求第100个fibonacci数，只需要将矩阵 
[0,1]乘上 
0 1 
1 1 
的一百次方，再取出第一项

因为我们知道，矩阵运算满足结合律，一次次右乘那个矩阵完全可以用乘上那个矩阵的N次方代替，更进一步，那个矩阵的N次方就是这样的形式： 
f(n-1) f(n) 
f(n) f(n+1)

而求矩阵的N次方，由于矩阵乘法满足结合律，所以我们可以用log(N)的算法求出——这个算法大家都会么？ 
一个是二分，一个是基于二进制的求幂

二分的原理：要求矩阵的N次方A(N)，设i=N/2若N%2==1， 则 A(N)=A(i)*A(i)*A(1)若N%2==0， 则 A(N)=A(i)*A(i)

基于二进制的原理：将N拆为二进制数，譬如13=1101那么 A^13= A^8 * A^4 * A^1 （这里^表示幂运算）

也就是说，由A^1开始，自乘得到A^2，然后自乘得到A^4，如果N对应位为1，则将这个结果乘到目标上去

这样的话，将所有乘法改为模乘，就可以得到一个较大Fibonacci数除以M的余数

若不用递归，其实类似

实现代码：

#include<iostream> using namespace std; // f(n)=f(i)*f(n-i-1)+f(i+1)*f(n-i) int tempA,tempB,tempC,tempD; void func(int n,int &a,int &b,int &c,int &d){if(n==1){a=0;b=c=d=1;return ;}if(n%2==0){func(n/2,a,b,c,d);tempA=a*a+b*c;tempB=b*(a+d);tempC=c*(a+d);tempD=c*b+d*d;a=tempA%1997;b=tempB%1997;c=tempC%1997;d=tempD%1997;return;}else{func(n/2,a,b,c,d);tempA=b*(a+d);tempB=a*a+b*(a+c+d);tempC=c*b+d*d;tempD=c*(a+b+d)+d*d;a=tempA%1997;b=tempB%1997;c=tempC%1997;d=tempD%1997;return;} } int main(){int n;while(cin>>n&&n!=0){int a,b,c,d;if(n<=2){cout<<1<<endl;continue;}else n-=2;func(n,a,b,c,d);cout<<(b+d)%1997<<endl;} return 0; }

总结

以上是生活随笔为你收集整理的斐波那契数列取模（大数）分治算法的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。