(HDUACM2010版_11)搜索入门

杭电 ACM

ACM程序设计杭州电子科技大学 刘春英 acm@

杭电 ACM

每周一星(10):

guangjiell

2014-4-27

杭电 ACM

第十一讲

一招制敌之搜索题

2014-4-27

杭电 ACM

统计信息：根据“信息学初学者之家”网站的统计， Ural(俄罗斯的Ural州立大学的简称 ，有名 的Ural Online Problem Set 就是该校的系 统)的题目类型大概呈如下的分布： 搜索 动态规划 贪心 构造 约10% 约15% 约5% 约5% 计算几何 纯数学题 数据结构 约5% 约20% 约5%2014-4-27

图论 约10% 其它 约25%4

杭电 ACM

引言“算法中最基本和常用的是搜索，这里要说的是，有 些初学者在学习这些搜索基本算法是不太注意剪枝， 这是十分不可取的，因为所有搜索的题目给你的测试 用例都不会有很大的规模，你往往察觉不出程序运行 的时间问题，但是真正的测试数据一定能过滤出那些 没有剪枝的算法。 实际上参赛选手基本上都会使用常用的搜索算法，题 目的区分度往往就是建立在诸如剪枝之类的优化上 了。 ”

——摘自《ACM竞赛之新人向导 》2014-4-27 5

杭电 ACM

什么是搜索算法呢？搜索算法是利用计算机的高性能来有目的地 穷举一个问题的部分或所有的可能情况，从 而求出问题的解的一种方法。

搜索过程实际上是根据初始条件和扩展规则 构造一棵解答树并寻找符合目标状态的节点 的过程。

2014-4-27

杭电 ACM

本讲主要内容

二分搜索 三分搜索 DFS BFS(略)

2014-4-27

杭电 ACM

第一部分：二分查找

假设给出若干个(可以很多)有序 的整数，请查找某个元素是否存在， 比如——请查找以上数列中是否存在某个整数(比如25), 若有，请输出其位置，否则请输出NO~2014-4-27 8

2 3 4 5 6 8 12 20 32 45 65 74 86 95 100

杭电 ACM

第一部分：二分查找2 3 4 5 6 8 12 20 32 45 65 74 86 95 100

head

mid

tail

再次提醒：二分查找的前提—— 数据的单调性2014-4-27 9

杭电 ACM

思考：

1、在一百万个元素里查找某个 元素大约需要比较多少次？

2、时间复杂度：O(logN)

2014-4-27

杭电 ACM

二分查找-例题1

HDOJ-2199

给出方程： 8*x4 + 7*x3 + 2*x2 + 3*x + 6 = Y 其中，实数Y满足 (fabs(Y) <= 1e10) 请输出x在区间[0,100]的解，结果精确到小数点 后4位。2014-4-27 11

杭电 ACM

题目分析

常规暴力枚举？ 当测试数据足够多->效率低下 指定区间内的单调性(如何证明?) 推荐方法：二分求解

2014-4-27

杭电 ACM

二分查找-参考代码1

//HDOJ-2199 #include <iostream> #include <cmath> using namespace std; double Y; double l, r, m; double f( double x ) { return 8*pow(x, 4.0) + 7*pow(x, 3.0) + 2*pow(x, 2.0) + 3*x + 6;} int main() { int t; scanf("%d", &t ); while( t-- ) { scanf("%lf", &Y ); if( f

(0) <= Y && Y <= f(100) ) { l = 0; r = 100; while( r - l > 1e-6 ) { m = (l + r) / 2; double ans = f(m); if( ans > Y ) { r = m - 1e-7; }else l = m + 1e-7; } printf("%.4lf\n", (l + r) / 2 ); }else printf("No solution!\n"); } }

2014-4-27

杭电 ACM

二分查找-例题2

HDOJ-2899

给出函数： F(x) = 6*x7 + 8*x6 + 7*x3 + 5*x2 - y*x 其中，实数y满足 (0<y < 1e10) 请输出x在区间[0,100]时函数F(x)的最小值， 结果精确到小数点后4位。2014-4-27 14

杭电 ACM

题目分析

指定区间内是否满足单调性? 显然不满足->不能直接二分 满足凸性？ 如何证明？ 极值点的特点？ 是否可以二分？15

2014-4-27

杭电 ACM

二分查找-参考代码2

//HDOJ-2899 #include <stdio.h> #include <math.h> const double eps = 1e-8; double y; double cal(double x){ return 42.0*pow(x,6.0)+48.0*pow(x,5.0)+21.0*pow(x,2.0)+10.0*x; } double ans(double x){ return 6.0*pow(x,7.0)+8.0*pow(x,6.0)+7.0*pow(x,3.0)+5.0*pow(x,2.0)-y*x; } int main(){ int T; double f,l,mid; scanf("%d",&T); while(T--){ scanf("%lf",&y); if(cal(100.0)-y<=0.0){ printf("%.4lf\n",ans(100.0)); continue; } f=0.0,l=100.0; while(l-f>eps){ mid=(f+l)/2.0; if(cal(mid)-y<0.0){ f=mid; }else{ l=mid; } } printf("%.4lf\n",ans(mid)); } return 0;

2014-4-27

杭电 ACM

新问题

如果函数满足凸性特点， 但是——求导不方便！ 该如何处理？

2014-4-27

杭电 ACM

三分查找(Ternary Search)

2014-4-27

杭电 ACM

三分查找(Ternary Search)

2014-4-27

杭电 ACM

三分查找(Ternary Search)

2014-4-27

杭电 ACM

三分查找(Ternary Search)

2014-4-27