浅谈二分策略的应用65730.pptx
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《浅谈二分策略的应用65730.pptx》由会员分享,可在线阅读,更多相关《浅谈二分策略的应用65730.pptx(29页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、二分策略二分策略在信息学竞赛中的应应用用华东师大二附中 杨俊3/24/20231WinterCamp 2005二分策略v来源来源 一个很简单的想法一个很简单的想法在在最坏情况下最坏情况下排除排除尽可能尽可能多多的干扰,以尽可能快地求得目标的干扰,以尽可能快地求得目标v效率效率 高!对信息的充分利用,尽可能去除冗余高!对信息的充分利用,尽可能去除冗余,减,减少了不必要计算少了不必要计算v应用应用 广!广!3/24/20232WinterCamp 2005三种应用类型v类型一:二分查找类型一:二分查找应用于一般有序序列应用于一般有序序列v类型二:二分枚举类型二:二分枚举应用于退化了的有序序列应用于
2、退化了的有序序列v类型三:二分搜索类型三:二分搜索应用于无序序列应用于无序序列3/24/20233WinterCamp 2005类型一:二分查找应用于一般有序序列 v申明:“有序序列”,仅包含两层意思:第一,它是一个第一,它是一个序列序列,一维的,一维的第二,该序列是第二,该序列是有序有序的,即序列中的任意两个元的,即序列中的任意两个元素都是可以比较的,也就是拥有我们平时素都是可以比较的,也就是拥有我们平时所说的所说的全序关系全序关系3/24/20234WinterCamp 2005类型一:二分查找应用于一般有序序列 v二分查找的一般实现过程:二分查找的一般实现过程:(1)确定查找范围)确定查
3、找范围(2)选择基准元素)选择基准元素(3)关键字比较,确定更精确的范围)关键字比较,确定更精确的范围(4)判断结果,如不够精确,转至()判断结果,如不够精确,转至(2)3/24/20235WinterCamp 2005例一:顺序统计问题v问题描述问题描述 给定一个由给定一个由n个不同的数组成的集合个不同的数组成的集合S,求,求其中第其中第i小的元素。例如:小的元素。例如:S=3,7,2,6,8,1,5,i=4Answer=53/24/20236WinterCamp 2005问题的一般解法v二分查找的过程:(1)确定待查找元素在)确定待查找元素在S中中(2)在)在n个元素中个元素中随机随机取出
4、一个记为取出一个记为x,将,将x作基准作基准(3)设)设S中比元素中比元素x小的有小的有p个个(4)如果找出)如果找出x,输出;否则转至(,输出;否则转至(2)v因为x是随机选出的,由简单的概率分析,可得算法的复杂度期望值为O(n)。如果如果ip,我们将范围确定为,我们将范围确定为S中比中比x大的大的元素,求该范围内第元素,求该范围内第i-p-1个元素;个元素;3/24/20237WinterCamp 2005小结v举这个例子,是想说明两点:举这个例子,是想说明两点:第一,二分查找第一,二分查找=logn第二,二分查找第二,二分查找=平均平均?3/24/20238WinterCamp 2005
5、类型二:二分枚举应用于退化了的有序序列 v与类型一中的二分查找相比,最大的区别在于这里的二分在判断选择哪一个部分递归调用时没有了比较运算*。显式显式有序序列有序序列隐含的退化了的隐含的退化了的有序序列有序序列3/24/20239WinterCamp 2005例二:BTP职业网球赛v问题描述问题描述N(N65536)有有N头奶牛(头奶牛(N是是2P)参加网球淘汰赛。即)参加网球淘汰赛。即N头奶牛分成头奶牛分成N/2组,每组两头奶牛比赛,决出组,每组两头奶牛比赛,决出N/2位胜者;所有胜者继而分成位胜者;所有胜者继而分成N/4组比赛组比赛直至剩下一头牛是冠军。直至剩下一头牛是冠军。K(1KN-1)
6、比赛既要讲求实力,又要考虑到运气。每头比赛既要讲求实力,又要考虑到运气。每头奶牛都有一个奶牛都有一个BTP排名,恰为排名,恰为1N。如果两。如果两头奶牛的排名相差大于给定整数头奶牛的排名相差大于给定整数K,则排名靠,则排名靠前的奶牛总是赢排名靠后的奶牛;否则,双前的奶牛总是赢排名靠后的奶牛;否则,双方都有可能获胜。方都有可能获胜。Answer 现在观众们想知道,哪头奶牛是所有可能成现在观众们想知道,哪头奶牛是所有可能成为冠军的牛中排名最靠后的。并要求你列举为冠军的牛中排名最靠后的。并要求你列举出一个可能的比赛安排使该奶牛获胜。出一个可能的比赛安排使该奶牛获胜。3/24/202310Winter
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 浅谈 二分 策略 应用 65730
![提示](https://www.deliwenku.com/images/bang_tan.gif)
限制150内