浅析倍增思想在信息学竞赛中的应用_第1页
浅析倍增思想在信息学竞赛中的应用_第2页
浅析倍增思想在信息学竞赛中的应用_第3页
浅析倍增思想在信息学竞赛中的应用_第4页
浅析倍增思想在信息学竞赛中的应用_第5页
已阅读5页，还剩30页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

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

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论