论文--浅析倍增思想在信息学竞赛中的应用

《论文--浅析倍增思想在信息学竞赛中的应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、浅析倍增思想在信息学竞赛中的应用浅析倍增思想在信息学竞赛中的应用目录Ø摘要2Ø关键字2Ø正文2u引言2u应用之一在变化规则相同的情况下加速状态转移2u应用之二加速区间操作8u一个有趣的探讨11Ø总结12Ø感谢12Ø参考文献13Ø附录13第29页共29页浅析倍增思想在信息学竞赛中的应用摘要倍增思想是解决信息学问题的一种独特而巧妙的思想。本文就倍增思想在信息学竞赛中两个方面的应用进行了分析。全文可以分为五个部分：第一部分引言，简要阐述了倍增思想的重要作用以及运用方法；第二部分介绍倍增思想的第一个应用——在变化规则相同的情况下加速状态转移

2、；第三部分介绍倍增思想的第二个应用——加速对区间进行的操作；第四部分探讨了一个有趣的问题，即为什么倍增思想每次只将考虑范围扩大一倍而不是两倍、三倍等；第五部分总结全文，再次指出倍增思想的重要性以及应该怎样灵活运用倍增思想。关键字倍增思想变化规则状态转移区间操作正文引言倍增思想是一种十分巧妙的思想，在当今的信息学竞赛中应用得十分广泛。尽管倍增思想可以应用在许多不同的场合，但总的来说，它的本质是：每次根据已经得到的信息，将考虑的范围扩大一倍，从而加速操作。大家所熟悉的归并排序实际上就是倍增思想的一个经典应用。在解决信息学问题方面，倍增思

3、想主要有这两个方面的应用——一、在变化规则相同的情况下加速状态转移；二、加速区间操作。下文将就这两个方面进行详细的讨论。倍增思想应用之一在变化规则相同的情况下加速状态转移这里是指由一种状态变化到另一种状态，并不只限于动态规划中的“状态转移”。首先，让我们来看一个简单的例子——已知实数a，计算a17。分析：很显然，一种最简单的方法就是令b=a，然后重复16次进行操作b=b*a.这样，为了得到a17，共进行了16次乘法。第29页共29页浅析倍增思想在信息学竞赛中的应用现在考虑另外一种方法，令a0=a,a1=a2,a2=a4,a3=a8,

4、a4=a16,可以看出，ai=ai-12,(1<=i<=4)。于是，得到a0,a1,a2,a3,a4共需要4次乘法。而a17=a*a16=a0*a4,也就是说，再进行一次乘法就可以得到a17.这样，总共进行5次乘法就算出了a17.如果将这种方法推而广之，就可以解决这样一个一般性的例题：例1、已知，计算:分析：1、将n表示成为二进制形式并提取出其中的非零位，即n=2b1+2b2+……+2bw，不妨设b1

5、幂运算的法则，可以推出==**……*，而这些数都已经被求出，所以最多再进行(bw+1)次操作就可以得到。由于n的二进制表示最多有个非零位，所以bw最大为。也就是说，最多进行O()次乘法就可以算出，这比进行O(n)次乘法效率高得多。当然，由于得到n的二进制表示的过程本身就是按照从低位到高位的顺序，所以并不需要记录，，，……，，只需要每次即算即用就可以了。伪代码如下（见下页）：那么，这个算法是如何减少乘法次数的呢？显然，==**……*使得求转化为求不超过个a的幂的积。而序列，，，……，中除了第一个数以外，每一个数都是前一个数的平方。即在

6、从得到的过程中，按照原始的方法需要进行2i次乘法操作，而现在只需要利用已知结果进行一次乘法操作（*=）即可。大大减少了操作次数，从而降低了时间复杂度。第29页共29页浅析倍增思想在信息学竞赛中的应用longdoublepower(longdoublea,longn){longdoubleb,result;result=1;b=a;while(n){if(n%2)result*=b;b*=b;n/=2;}returnresult;}算法1.1而在实际情况中，a可能是一个实数，也可能是一个矩阵或是一个抽象的状态。变化规则也可能是其他操作

7、（如矩阵乘法、动态规划的状态转移等）。但是只要符合以下两个条件，就可以应用倍增思想并采用类似于上面的方法加速计算：1、每次的变化规则必须相同；2、变化规则必须满足结合律。具体到上面的例子，每次的变化规则都是乘法，而乘法是满足结合律的。下面将通过另一个例子更加深入地探讨倍增思想在加速状态转移方面的应用，同时得到更精确的定义。例2、骰子的运动CEPC2003ProblemDDiceContest给定一个六个面的骰子，每个面上都有一定的权值（1到50之间的整数）。骰子运动的范围是一个宽度为4，向左右无限延伸的带子（如图1.1）。带子从左到

8、右的横坐标值为……，-3，-2，-1，0，1，2，3，……，从前到后的纵坐标值依次为1，2，3，4（这里的坐标对应的都是格子，而不是点）。这样，带子被分成了无限多个格子。每个格子恰好能与骰子的一个面完全重合。骰子每次可以向前后左右中的