资源描述：
《倍增思想的研究》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、倍增思想的研究安徽省芜湖市第一屮学朱晨光刖a倍增思想是信息学中一种非常重要的思想，近几年屮越来越受到人们的重视，应用也日趋广泛。倍增思想的本质并不复杂，但是要想在特定的题目中恰当地运用好倍增思想却并不容易。因此，木文将从两个方面的运用来探讨倍增思想,并在其中总结倍増思想的实质与理论基础。关键字倍增思想正文倍增思想是一种十分巧妙的思想。“倍增”二字体现在它毎次将当前的已知结果或考察范围扩大一倍。正是由于这个原因，它的时间复杂度降低了很多，一般是将一个系数N变为log2No举一个简单的例子，如果我们想把1变成16,可以每次加1,这样需要
2、操作15次；还可以每次将当而的数乘以2,这样只需耍操作4次。这述只是针对16这个比较小的数。如果是32768(215),1048576(220),2147483648(2^),……,那么节省的操作次数就非常多了。因此，在这里，我们先对倍增思想有一个感性的认识——即每次通过“翻番”来减少操作次数。倍增思想的运用是十分广泛的。一般來说，有如下两种情况：一、将一个状态经过若干次变化得到另一个状态，而每次变化的规则都是相同的。这时，可以借助倍增思想，每次将考察的网个状态之间的距离
3、增大一倍，从而减小吋间复杂度；二、每次需要对一段区间进行某种
4、操作(一•般是统计操作)。这时可以利用倍增思想，在预处理中得到这段区间中的每一点向后长度为2°,21,22,……(包括自己)的子区间的某种性质，以便在处理屮0(1)或O((log2N)x)地取用。下面，将就上面每种情况进行分析，并举出例题具体说明。情况一变化规则相同的情况下用倍增思想加速状态转移首先举一个小例子：在求320W,可以用3*3*3*……*3实现，共要做19次乘法。还可以将32°分解为3,6*34,并且可以由3经一次乘法得到32,3?经一•次乘法得到34,3°经一次乘法得到3*,38经一次乘法得到3"。因此，只需要4次乘法
5、就可以得到所需要的3"与34,再进行一次乘法就得到了3笔总共只需要5次乘法。那么，在这里倍增思想究竟是如何减少了运算次数呢？让我们先将这种方法若A状态需要经过x次变化得到B状态，则称A与B的距离是x.做一个归纳:n在求a时，如果a的乘法运算满足结合率，那么就可以任意地决定这(n-l)次乘法操作的顺序。而倍增思想是这样做的：第一步：将n表示成为2b,+2b2+……+2代其中，bl>b2>……>bw>=0.很明显,这一步操作可以通过将n表示成为一个二进制数实现，若第x位为1,则x必等于某个bi.为了后而处理方便，这里建立一个集合B={b
6、l,b2,……,bw}.%1亠%2亠.^hwob1%2第二步：根据幕运算的有关规则,aM……=a^*……•这为第三步指明了方向：即高效地求出。,a,……,a。2°?z第三步：由于已知a,即a,因此可以每次将当前结果进行平方，即由茁得到,即•另设一个result,初值为1。如果当前结果为且iwB,2’则令result^-result*Cl.这样，在取遍了B集合中每一个值后，result便为最终结果那么，这样的操作需要进行多少次呢？根据二进制数的性质，十进制数n的二进制表示一定不超过Llog2/7.J+1位。也就是说，其屮最多有
7、_lo
8、g2hJ+1个12。且最高位是第Liog2/iJ+i位.因此，a最多进行Liog2nJ次平方操作就可以得到2加所有需要的值。而对于每个还要与result进行一次乘法操作，所以总的乘法操作次数最多为2Llog2//J+l,是0(log?"级别的。其中省去的乘法操作很好理解：举一个例子，在从Q丁得到小的过程屮，按照原始的方法需要进行乞次2’乘法操作，而现在只需要利用已知结果进行一次乘法操作即可。大大减少了操作次数，从而降低了时间复杂度。实际运用屮，这个a并不仅仅可以表示一个实数，还可以是-•个短阵或是一个抽象意义上的状态。从这个归纳中，
9、可以看出，倍增思想在这种情况下的运用具有如下性质：1、求从一个状态经过n次相同规则的变化得到的另一个状态；2、这种规则下的变化具有结合率。在这种情况下，只需要将n表示成为一些互不相等的2的幕的和，然后利用幕运算的有关性质，将求转化为求一些a的2的乘方的幕2的乘积。而从a即2"2a的2的乘方的幕即指。o2°a开始，每次进行平方操作，即可在O(log2n)时间内得到问题的解。下面举一些例题进行说明：例1、有一个N*N的矩阵A,求矩阵Ak(即K个A连乘后的结果)，其中每一个数都为对10000取模后的值。注意：矩阵乘法具有结合率。分析：经过
10、对上面那个小例子的深入探究，这题就变得十分简单了。只要将例子屮实数a变为矩阵A即可。吋间复杂度为O(N3*log2K),空间复杂度为O(Nl例2、骰子的运动给定一个六个面的骰子，每个面上都有一定的权值(1到50之间的整数)。骰子运动的
