浅析倍增思想 在信息学竞赛中的应用 安徽省芜湖市第一中学 朱晨光引言它的本质思想是每次根据已经得到的信息，将考虑的范围扩大一倍 ，从而加速操作。倍增思想是一种十分巧妙的思想，在当今的信息 学竞赛中应用得十分广泛。引言在解决信息学问题方面，倍增思想主要有这两个方 面的应用一、在变化规则相同的情况下加速状态转移二、加速区间操作倍增思想应用之一 在变化规则相同的情况下加速状态转移 首先，让我们来看一个简单的例子已知实数a，计算an。 很显然，一种最简单的方法就是令b=a，然后重复(n-1)次 进行操作b=b*a.这样，为了得到an，共进行了(n-1)次乘法。现在考虑另外一种方法例一将n表示成为二进制形式并提取出其中的非零位，即 n=2b1+2b2+2bw，不妨设b1=2)的倍增思想为 k增思想，则本文所介绍的倍增思想为2增思想。 一个有趣的探讨对于k增思想，最多通过 次扩大就可以得到所 有需要的值，这里为了讨论方便，简化为logkN. 但是，为 了每次扩大(k-1)倍，必须操作(k-1)次。所以时间复杂度 为O(k-1)logkN)。本文中k=2，因此复杂度为(2-1)log2N=log2N.一个有趣的探讨为了将k=3与k=2进行比较。这里采用商值比较法：=一个有趣的探讨也就是说，当k3时f(k)为增函数，即恒有 f(k)f(2)=0，即(k-1)-log2k0，k-1 log2k. 令f(k)=(k-1)-log2k.当k=2时，f(k)=0；当k3时f(k)=1- =1- 1- 0.51910一个有趣的探讨y1=k-11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 168 7 6 5 4 3 2 1 0y2=log2kky一个有趣的探讨这就从数学角度解释了倍增思想的高效性!总结 倍增思想 应用加速状态转移加速区间操作恰当利用计算结果不存在冗余的运算高效简洁独辟蹊径总结倍增思想1，2，4，8，16，32，在思考中体会内涵在实战中积累经验自然融入到 思考过程中指导自己解 决各类问题举重若轻 挥洒自如总结纸上得来终觉浅绝知此事要躬行谢谢应用之一的其他实现方法当然，这个应用还有一些其他的实现方法。比如在 计算an时,不一定要计算a1,a2,a4,a8，可以按照如下 的规则进行递归：a n=1，an= an/2*an/2 n为偶数，a(n-1)/2* a(n-1)/2*a n为奇数.很显然，这种算法的时间复杂度也是O(log2N)，这 也说明倍增思想在实际操作中是灵活多变的，要根据实 际情况选择相对简便的形式加以利用。小结二需要再次强调的是，这里的变化规则必须相同（这 比较容易检验）并且满足结合律。一个不满足结合律的 运算除法就不能用倍增思想求解（除非转化成乘法 ）：a1/a2/a3/a4/ana1/(a2/a3/a4/an)。这也提醒 我们，在运用倍增思想解题之前，必须检验是否可行。 如果不满足条件，就要构造出合法的变化规则或者思考 其他的方法。