(lecture08)刘春英搜索入门

《(lecture08)刘春英搜索入门》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、ACM程序设计计算机学院刘春英7/11/20211今天，你了吗？诚信7/11/20212第十讲一招制敌之搜索题7/11/20213根据“信息学初学者之家”网站的统计，Ural（俄罗斯的Ural州立大学的简称，那里设立了一个UralOnlineProblemSet，并且支持OnlineJudge。）的题目类型大概呈如下的分布：搜索动态规划贪心构造图论约10%约15%约5%约5%约10%计算几何纯数学问题数据结构其它约5%约20%约5%约25%统计信息：7/11/20214搜索题特点分析:题意容易理解算法相对固定编

2、程有路可循竞赛必备知识7/11/20215——摘自《ACM竞赛之新人向导》“算法中最基本和常用的是搜索，主要是回溯和分支限界法的使用。这里要说的是，有些初学者在学习这些搜索基本算法是不太注意剪枝，这是十分不可取的，因为所有搜索的题目给你的测试用例都不会有很大的规模，你往往察觉不出程序运行的时间问题，但是真正的测试数据一定能过滤出那些没有剪枝的算法。实际上参赛选手基本上都会使用常用的搜索算法，题目的区分度往往就是建立在诸如剪枝之类的优化上了。”引言7/11/20216什么是搜索算法呢？搜索算法是利用计算机的高性能来

3、有目的地穷举一个问题的部分或所有的可能情况，从而求出问题的解的一种方法。搜索过程实际上是根据初始条件和扩展规则构造一棵解答树并寻找符合目标状态的节点的过程。7/11/20217预热一下：二分查找2345681220324565748695100headmidtail7/11/20218查找示意图：A[1]~A[15]A[1]~A[7]A[9]~A[15]A[1]~A[3]A[5]~A[7]A[1]~A[1]A[3]~A[3]……7/11/20219思考：1、在一百万个元素里查找某个元素大约需要比较多少次？2、时间

4、复杂度：O(logN)7/11/202110举例分析从一道数值型搜索题讲起7/11/202111HDOJ_1239CallingExtraterrestrialIntelligenceAgain题目链接SampleInput5129999999999916805161970112002411000SampleOutput223133132373434337537/11/202112获取有用信息a.给定整数m,a,b(4

5、设为p,q)满足以下条件：p,q均为质数；p*q<=m;a/b<=p/q<=1;c.输出所有满足以上条件的p,q中乘积最大的一对p,q7/11/202113算法分析1.典型的搜索从所有可能的p,q中寻找满足条件的一对2.p,q的要求p,q均为质数,且p<=q<=100000;3.按上述思想流程应为a.从1—100000中搜出质数b.两层循环，试遍所有的组合(p,q可能相等）c.每种组合去判断是否符合条件，如是，将p*q与当前最大值比较，判断，保存7/11/202114面临的问题：超时！从1—100000的质数运算

6、约为1e+8,而这只是准备工作。因此，如不加以分析简化此题无法在规定时间内出解7/11/202115深入分析考虑大于10000的某个质数，不妨设为Q，另一个质数为P，则：然而，这是最小的范围吗？p,q的范围其实可在2—50000(why?)如果P<10，P/Q<0.001如果P>10，P*Q>100000而考虑到a,b的取值范围(1<=a<=b<=1000)可知min(a/b)=0.001同时，要求：p*q<=m<=100000所以无论如何质数都不能超过10000。（事实上，不会超过9091）7/11/20211

7、6搜索时的技巧：搜索顺序很重要。建议从大往小搜（num:质数的个数）for(i=num-1;i>=0;i--)for(j=i;j<=num-1;j++)……注意剪枝：If(a[j]>m

8、

9、a[j]*a[i]>m

10、

11、((double)a[i]/a[j])

12、空间。7/11/202119初始状态：目标状态：2831647512384765例九宫重排问题7/11/20212028316475283147652831647583214765283147652318476528316475283147652318476523184765283714657/11/202121231847651238476512384765123784