《算法合集之《运用化归思想解决信息学中的数列问题》》由会员分享，可在线阅读，更多相关《算法合集之《运用化归思想解决信息学中的数列问题》（28页珍藏版）》请在金锄头文库上搜索。
1、福建省福州市第一中学,余林韵,运用化归思想解决信息学中的数列问题,1、1、1、2、1 1、1、1、2、1 ,走队列喊口号,日常生活中,年份,2006，2007，2008，2009,按某种法则排列着的一列数,数列,解决数列问题,知识！,化归、猜想！,化归,就是转化和归结,问题甲,比较容易解决的问题乙,化归方法的要素,化归对象 即对什么东西进行化归 化归目标即化归到何处去 化归途径即如何进行化归,Dispute (Ural 1309),数列Fn满足：其中给定n，求解Fn。,数据规模0=N=108,Dispute (Ural 1309),数据规模太大,化归到小规模,?,Dispute (Ural 1
2、309),分而治之！,算法一,预处理，求出数列F的所有项 将所有的F100000k保存下来 当给定N的时候，我们可以先找到离N最接近的一项F100000k 简单的递推即可解决,复杂度：O(100000),将数据规模继续扩大,?,拓展,Dispute (Ural 1309),Dispute (Ural 1309),算法一不能胜任,108s=27777h=1157d3年,黄花菜都凉了,Dispute (Ural 1309),算法一分割的太暴力！,如何“温柔”一些？,再次观察数列,函数gx,y 的特点：gx,y =(y-1)*x5+x3-xy+3x+7y) mod 99731、所有项y的指数非0即1
3、 2、式子的最后取模了一个质数9973,性质1,把x看作一个常数，整理后可得：gx,y=(x5-x+7)y +(-x5+x3+3x) mod 9973 数列Fn是个1阶线性递推数列。 联想：计算常系数线性递推数列的第N项可以利用矩阵乘法的方法 调整化归目标：看看能否通过合理的分段，将数列变成常系数线性递推数列。,性质2,令M=9973 则有常数A,B使得：Fkm=A*F(k-1)m+B，,成功化归！,其余三道例题,ABS序列（Top Coder SRM 369 - Div 1 - 500 Points）Count（NOI2007）Maximum. Version 2（Ural 1396）,Ti
4、me Limit,总结,数列问题千变万化，化归不是万能的,牢牢抓住问题的本质,认真仔细观察，敢于大胆猜想 富有创新精神，发现数列的美,走向成功！,谢谢大家,欢迎提问,性质2的证明,令Ui=(j5-j+7) mod M, Vi=(-j5+j3+3*j) mod M, j=i mod M + 1 Fi+1= Ui *Fi+Vi FKM+1=(UKM+1*FKM+VKM+1) mod M FKM+2=(UKM+2*FKM+1+VKM+2) mod M FKM+3=(UKM+3*FKM+2+VKM+3) mod M F(K+1)M=(U(K+1)M*F(K+1)M-1+V(K+1)M) mod M,性
5、质2的证明,F(K+1)M=(U(K+1)M*F(K+1)M-1+V(K+1)M) mod M=(U(K+1)M*(U(K+1)M-1*F(K+1)M-2+V(K+1)M-1 )+V(K+1)M) mod M=(U(K+1)M*U(K+1)M-1*F(K+1)M-2+U(K+1)M*V(K+1)M-1+V(K+1)M) mod M,性质2的证明,F(K+1)M=(A*FKM+B) mod MUi=(j5-j+7) mod M=Ui=U(i+M) Vi=(-j5+j3+3*j) mod M=Vi=V(i+M) A,B为定值,计算常系数线性递推数列的第N项,矩阵乘法：两个矩阵A,B，A=(ai,j
6、)n*m,B=(bi,j)m*t复杂度：O(NMT) 满足结合律，即,计算常系数线性递推数列的第N项,递推数列 一个数列的连续项之间的关系叫递推关系，由递推关系确定的数列叫递推数列 常系数线性递推数列 由初始值和方程an+k=F(an+k-1,an)的数列an称为k阶递推数列 特别的，当方程形如下式的时候数列an称为k阶常系数线性递推数列。an+k=c1an+k-1+c2an+k-2+ckan+f(n)，这里c1,c2ck为常数，其中ck0 如果f(n)=0,那么数列an称为k阶常系数齐次线性递推数列。,计算常系数线性递推数列的第N项,以广义Fibonacci数列为例： F1=a,F2=b,FN=FN-1+FN-2 观察数列前几项： F3=F1+F2=a+b F4=F2+F3=F2+(a+b)=a+2b F5=F3+F4=(a+b)+(a+2b)=2a+3b 数列的任意一项都是由若干个a与b相加组成的！,计算常系数线性递推数列的第N项,用矩阵乘法解决：,
