问题:递推数列【BAIDU】:给定a0,a1,以及an=p*a(n-1)+q*a(n-2)中的p,q。这里n>=2。求第k数对10000的模。
要求性能尽可能优化。
说明:所给出的程序的输入包括a0,a1,p,q,k,输出第k个数a(k)对10000的模。
答:初看这个题目,第一印象就是无非考考递归程序设计或者线性递推罢了。其实仔细想了想题目要求性能尽可能优化,简单地使用递归或者线性递推的设计显然不能达到要求,在实际编程中也验证了这一点,使用递归的设计方法的时候,当k增加到300左右程序就不动了,效率非常低,使用线性递推的时间复杂度可以达到O(n),但是对于一个大k来说复杂度还是有优化的余地。思前想后,我觉得使用矩阵二分乘法来对付大k的情况还是可行的,下面算法,对超过1000的k值,利用前置矩阵计算的结果,可以大大减少计算的次数。算法的实现如下:
#include <stdio.h>
typedef struct matrix{
int k;
long a[2][2];
}Matrix;
int main(){
long q,p,a0,a1;
int i,s,t,k;
Matrix m[30];
for(;scanf("%ld%ld%ld%ld%d",&a0,&a1,&p,&q,&k)!=EOF;){
t=0;
//For k=2
m[0].k=1;
m[0].a[0][0]=0; m[0].a[0][1]=q%10000;
m[0].a[1][0]=1; m[0].a[1][1]=p%10000;
if(k-1<=m[0].k) goto CALC;
//For k=3
t=1;
m[1].k=2;
m[1].a[0][0]=m[0].a[0][1]; m[1].a[0][1]=(q*p)%10000;
m[1].a[1][0]=m[0].a[1][1]; m[1].a[1][1]=(q+p*p)%10000;
if(k-1==m[1].k) goto CALC;
//For k=4
t=2;
m[2].k=3;
m[2].a[0][0]=m[1].a[0][1]; m[2].a[0][1]=(q*q+q*p*p)%10000;
m[2].a[1][0]=m[1].a[1][1]; m[2].a[1][1]=(2*q*p+p*p*p)%10000;
if(k-1==m[2].k) goto CALC;
//For k=5
t=3;
m[3].k=4;
m[3].a[0][0]=m[2].a[0][1]; m[3].a[0][1]=(2*q*q*p+q*p*p*p)%10000;
m[3].a[1][0]=m[2].a[1][1]; m[3].a[1][1]=(q*q+3*q*p*p+p*p*p*p)%10000;
if(k-1==m[3].k) goto CALC;
//For k=6
t=4;
m[4].k=5;
m[4].a[0][0]=m[3].a[0][1]; m[4].a[0][1]=(q*q*q+3*q*q*p*p+q*p*p*p*p)%10000;
m[4].a[1][0]=m[3].a[1][1]; m[4].a[1][1]=(3*q*q*p+q*p*p*p+3*q*p*p+p*p*p*p*p)%10000;
if(k-1==m[4].k) goto CALC;
t=4;s=5;
if(k-1>=10){
for(;m[t].k+s<k;++t){
m[t+1].k=m[t].k+s; //大k加速
m[t+1].a[0][0]=(m[t].a[0][0]*m[t].a[0][0]+m[t].a[0][1]*m[t].a[1][0])%10000;
m[t+1].a[0][1]=(m[t].a[0][0]*m[t].a[0][1]+m[t].a[0][1]*m[t].a[1][1])%10000;
m[t+1].a[1][0]=(m[t].a[1][0]*m[t].a[0][0]+m[t].a[1][1]*m[t].a[1][0])%10000;
m[t+1].a[1][1]=(m[t].a[1][0]*m[t].a[0][1]+m[t].a[1][1]*m[t].a[1][1])%10000;
s+=s;
}
}
for(;k!=m[t].k+1;){
i=t;
while(m[t].k+m[i].k>k-1 && i>0) --i;
m[t+1].k=m[t].k+m[i].k;
m[t+1].a[0][0]=(m[t].a[0][0]*m[i].a[0][0]+m[t].a[0][1]*m[i].a[1][0])%10000;
m[t+1].a[0][1]=(m[t].a[0][0]*m[i].a[0][1]+m[t].a[0][1]*m[i].a[1][1])%10000;
m[t+1].a[1][0]=(m[t].a[1][0]*m[i].a[0][0]+m[t].a[1][1]*m[i].a[1][0])%10000;
m[t+1].a[1][1]=(m[t].a[1][0]*m[i].a[0][1]+m[t].a[1][1]*m[i].a[1][1])%10000;
++t;
}
CALC:
{
if(t==0) {
if(k==0){
printf("%ld\n",a0%10000);
}else if(k==1){
printf("%ld\n",a1%10000);
}else{
printf("%ld\n",(a0*m[t].a[0][1]+a1*m[t].a[1][1])%10000);
}
}else{
printf("%ld\n",(a0*m[t].a[0][1]+a1*m[t].a[1][1])%10000);
}
}
}
return 0;
}
运行结果:
- 大小: 14.8 KB
分享到:
相关推荐
2019互联网面试题第2季
国内一线互联网公司面试题整理,包括 BAT TMD。帮助你顺利度过面试难关!
172份,7701页互联网大厂面试题 172份,7701页互联网大厂面试题 172份,7701页互联网大厂面试题
互联网架构面试题
互联网企业面试真题 深圳-OPPO.pdf 深圳-银盛支付-Java中级.pdf 深圳-中国平安-Java中级.pdf 深圳-商汤科技.pdf 深圳-腾讯.pdf 深圳-乐信.pdf 深圳-蚂蚁金服.pdf 上海-携程.pdf 深圳-丰巢科技.pdf 厦门-中软国际-...
互联网工作的面经,以及大部分互联网面试真题,另外还有招商银行的面试真题
这份资源包括多个互联网公司的面试内容,包括BAt在内,还有小米,网易,搜狗,以及其他一系列公司,内容有C,C++等
最新一线互联网公司面试题库,经验分享,复习后面试通过几率大大增加,好好准备才有机会,包含通信,网络,数据结构,算法,高并发,多线程
ava工程师面试题大全-100%公司笔试题你都能碰到几个.docx Java开发工程师上机笔试题.docx Java开发求职面试题.docx Java开发笔试题.docx Java数据结构类面试题.docx Java数据结构题.docx Java笔试面试宝典.docx Java...
BTA面试题总结,相信会对大家又不小的帮助,祝你面试成功。
各大互联网公司面试题一网打尽。。。。。。。。。。。。。。。。
2019,尚硅谷,周阳,互联网面试题脑图,第2季,.mmap版
内容概要:本书从近一百套最新一线互联网公司面试题中精选而出,涵盖Java架构面试所有技术栈,包 括JVM,Mysql,并发,Spring,Mybatis,Redis,MQ,Zookeeper,Netty, Dubbo,Spring Boot,Spring Cloud,数据结构...
java面试题互联网大厂面试题
2020互联网面试题第2季 2020互联网面试题第2季 2020互联网面试题第2季 2020互联网面试题第2季 2020互联网面试题第2季 2020互联网面试题第2季
阿里、百度、腾讯、华为、网易、等各种互联网笔试面试题合集。
1000道 互联网Java工程师面试题
互联网校园招聘的一些面试题 互联网校园招聘的一些面试题
2019年一线互联网公司Java高级面试题总结 面试很有用!
BAT及各大互联网公司2014前端笔试面试题:HTML