斐波那契数列取模(大数)分治算法
斐波那契数列取模(大数)分治算法
这是算法课程上完分之策略后老师留的一道题目: 菲波那契数列如下: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'和b'来继续这一运算 如果大家熟悉利用“矩阵”这一工具的话,就知道,如果把a、b写成一个向量[a,b],完成上述操作相当于乘以矩阵? 因为我们知道,矩阵运算满足结合律,一次次右乘那个矩阵完全可以用乘上那个矩阵的N次方代替,更进一步,那个矩阵的N次方就是这样的形式:? 而求矩阵的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,255)">int &b,255)">int &c,255)">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/return; } } int main(){ int n; while(cin>>n&&n!=0){ int a,d; if(n<=2){ cout<<1<<endl; continue; } else n-=2; func(n,d); cout<<(b+d)%1997<<endl; } return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |