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