北京大学暑期课《acmicpc竞赛训练》

《北京大学暑期课《acmicpc竞赛训练》》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、北京大学暑期课《ACM/ICPC竞赛训练》北京大学信息学院郭炜guo_wei@PKU.EDU.CNhttp://weibo.com/guoweiofpku课程网页：http://acm.pku.edu.cn/summerschool/pku_acm_train.htm二分查找2二分查找A心里想一个1-1000之间的数，B来猜，可以问问题，A只能回答是或否。怎么猜才能问的问题次数最少？是1吗？是2吗？.......是999吗？平均要问500次大于500吗？大于750吗？大于625吗？......每次缩小猜测范围到上次的一半，只需要10次3

2、二分查找函数写一个函数BinarySeach，在包含size个元素的、从小到大排序的int数组a里查找元素p,如果找到，则返回元素下标，如果找不到，则返回-1。要求复杂度O(log(n))intBinarySearch(inta[],intsize,intp){intL=0;//查找区间的左端点intR=size-1;//查找区间的右端点while(L<=R){//如果查找区间不为空就继续查找intmid=L+(R-L)/2;//取查找区间正中元素的下标if(p==a[mid])returnmid;elseif(p>a[mid])L=m

3、id+1;//设置新的查找区间的左端点elseR=mid-1;//设置新的查找区间的右端点}return-1;}//复杂度O(log(n))4二分查找函数写一个函数LowerBound，在包含size个元素的、从小到大排序的int数组a里查找比给定整数p小的，下标最大的元素。找到则返回其下标，找不到则返回-1intLowerBound(inta[],intsize,intp)//复杂度O(log(n)){intL=0;//查找区间的左端点intR=size-1;//查找区间的右端点intlastPos=-1;//到目前为止找到的最优解w

4、hile(L<=R){//如果查找区间不为空就继续查找intmid=L+(R-L)/2;//取查找区间正中元素的下标if(a[mid]>=p)R=mid-1;else{lastPos=mid;L=mid+1;}}returnlastPos;5}二分查找函数注意：intmid=(L+R)/2;//取查找区间正中元素的下标为了防止(L+R)过大溢出:intmid=L+(R-L)/2;6二分法求方程的根求下面方程的一个根：f(x)=x3-5x2+10x-80=0若求出的根是a，则要求

5、f(a)

6、<=10-6解法：对f(x)求导，得f'(x

7、)=3x2-10x+10。由一元二次方程求根公式知方程f'(x)=0无解，因此f'(x)恒大于0。故f(x)是单调递增的。易知f(0)<0且f(100)>0,所以区间[0,100]内必然有且只有一个根。由于f(x)在[0,100]内是单调的，所以可以用二分的办法在区间[0,100]中寻找根。7二分法求方程的根#include#include#includeusingnamespacestd;doubleEPS=1e-6;doublef(doublex){returnx*x*x-5*x*x+

8、10*x-80;}intmain(){doubleroot,x1=0,x2=100,y;root=x1+(x2-x1)/2;inttriedTimes=1;//记录一共尝试多少次，对求根来说不是必须的y=f(root);while(fabs(y)>EPS){if(y>0)x2=root;elsex1=root;root=x1+(x2-x1)/2;5.70508593y=f(root);32triedTimes++;}printf("%.8f",root);printf("%d",triedTimes);return0;8}例题1输入n

9、(n<=100,000)个整数，找出其中的两个数，它们之和等于整数m(假定肯定有解)。题中所有整数都能用int表示9例题1输入n(n<=100,000)个整数，找出其中的两个数，它们之和等于整数m(假定肯定有解)。题中所有整数都能用int表示解法1：用两重循环，枚举所有的取数方法，复杂度是O(n2)的。for(inti=0;i

10、=100,000)个整数，找出其中的两个数，它们之和等于整数m(假定肯定有解)。题中所有整数都能用int表示解法2：1)将数组排序，复杂度是O(n×log(n))2)对数组中的每个元素a[i]