算法合集之《浅析倍增思想在信息学竞赛中的应用》.ppt

《算法合集之《浅析倍增思想在信息学竞赛中的应用》.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、浅析倍增思想在信息学竞赛中的应用安徽省芜湖市第一中学朱晨光引言它的本质思想是每次根据已经得到的信息，将考虑的范围扩大一倍，从而加速操作。倍增思想是一种十分巧妙的思想，在当今的信息学竞赛中应用得十分广泛。引言在解决信息学问题方面，倍增思想主要有这两个方面的应用——一、在变化规则相同的情况下加速状态转移二、加速区间操作倍增思想应用之一在变化规则相同的情况下加速状态转移首先，让我们来看一个简单的例子——已知实数a，计算an。很显然，一种最简单的方法就是令b=a，然后重复(n-1)次进行操作b=b*a.这样，为了得到

2、an，共进行了(n-1)次乘法。现在考虑另外一种方法例一将n表示成为二进制形式并提取出其中的非零位，即n=2b1+2b2+……+2bw，不妨设b1

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

4、延伸的带子。带子从左到右的横坐标值为……，-3，-2，-1，0，1，2，3，……，从前到后的纵坐标值依次为1，2，3，4。这样，带子被分成了无限多个格子。每个格子恰好能与骰子的一个面完全重合。骰子每次可以向前后左右中的一个方向滚动一格，但不能移出带子，花费是滚动后朝上的面所附带的权值。例二骰子的运动给定当前骰子位置的坐标与各个面的朝向，求将这个骰子移动到某个新位置所需的最小花费。（所给横坐标的绝对值小于等于109）。分析如果不考虑横坐标巨大的差值，本题完全可以用动态规划求解。方法是将每一格按照骰子的朝向拆分成24

5、种状态，然后按列进行动态规划得到最小花费。具体方法是从起点所在列的24*4=96个状态推到第二列96个状态，再推到第三列，第四列……，一直推到终点所在的列。每次都用Dijkstra算法算出从一列中某个状态转移到相邻的一列中某个状态的最小花费。时间复杂度是与横坐标差值n是同阶的。分析但是，由于n最大可达109，所以这个算法无论从时间还是空间上都难以满足要求。那么，是否可以采用倍增思想呢？答案是肯定的！下面，我们来验证这里是否存在一种变化规则符合运用倍增思想的要求——相同并符合结合律。分析设骰子从第1列某个状态A运动

6、到第2列某个状态B最少需要花费代价c,则骰子从第2列的状态A运动到第3列的状态B同样最少需要花费代价c！这就是一种“相同的变化规则”！更一般地，如果骰子从第i列某个状态A运动到第(i+k)列某个状态B最少需要花费代价c，则骰子从第j列的状态A运动到第(j+k)列的状态B也最少需要花费代价c.分析又由于前面所给出的算法是动态规划，而动态规划一个很重要的特点是具有最优子策略。阶段ⅠA段B段C段阶段Ⅱ阶段Ⅲ阶段Ⅳ阶段Ⅴ分析至此，我们证明了变化规则既满足相同性又满足结合律，可以运用倍增思想解决：……A……B……a1分析…

7、…a1……a2……a4…………分析*………………**…………初始状态……目标状态*……*分析本题中，Dijkstra算法所耗费的时间可以看成是常数（根据题目中骰子各面权值的取值范围可以算出必须考虑的点数为常数），每次倍增的时间为963，而倍增的次数为log2n，所以上述算法的时间复杂度为O(963log2N)。小结二从上题中，我们进一步加深了对倍增思想的理解，并且纠正了一个以前错误的认识：倍增思想所作用的对象实际上是变化规则，而并非具体的状态！倍增思想的作用是算出一个状态到另一个状态的变化量。也就是说，倍增思想计

8、算出的量与具体的状态是无关的，而仅与状态之间的关系有关。小结二将这个过程写成伪代码就是：DoublingAlgorithm(A,n){//a,b,c均为变化规则，a的初值由其他算法得到。如例2中a由Dijkstra算法得到c=b=a;while(n){if(n%2)c=c•b;b=b•b;n/=2;}B=A*c;returnB;}（A为原状态，B为末状态。“状态*变化规则