编写程序的基础算法

黑龙江省ACM竞赛2011年春季培训相关教材ACM/ICPC东北地区赛事组委会相关网站ACM/ICPC东北地区赛事组委会网址:acm.hrbeu.edu.cn第一章基础算法1.1分治1.2递归1.3枚举1.4贪心ACM/ICPC东北地区赛事组委会1.1分治给你16个硬币。16个硬币中有一个是伪造的，并且那个伪造的硬币比真的硬币要轻一些。你的任务是利用一个天平找出这个伪造的硬币。ACM/ICPC东北地区赛事组委会1.循环比较（15次）ACM/ICPC东北地区赛事组委会1.1分治2.两两比较（8次）3.分而治之（4次）1.1分治分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且为原问题性质相同。求出子问题的解，就可以得到原问题的解。ACM/ICPC东北地区赛事组委会1.1分治分治法解题的一般步骤：（1）分解，将要解决的问题划分成若干规模较小的同类问题；（2）求解，当子问题划分得足够小时，用较简单的方法解决；（3）合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。ACM/ICPC东北地区赛事组委会1.1分治分治法应用举例：（1）二分搜索技术；（2）归并排序，快速排序；（3）最近点对问题；ACM/ICPC东北地区赛事组委会1.2递归从前有座山，山里有座庙，庙里有个老和尚和小和尚，老和尚对小和尚说：“从前有座山，山里有座庙，庙里有个老和尚和小和尚，老和尚对小和尚说：“从前有座山……ACM/ICPC东北地区赛事组委会1.2递归Void故事（）{从前有座山；山里有座庙；庙里有个老和尚和小和尚；老和尚对小和尚说故事（）；}ACM/ICPC东北地区赛事组委会1.2递归通常我们面对的问题不是简单的重复：从前有座山，山里有座庙，庙里有个老和尚10和小和尚10，老和尚10对小和尚10说：“从前有座山，山里有座庙，庙里有个老和尚9和小和尚9，老和尚9对小和尚9说：“从前有座山……ACM/ICPC东北地区赛事组委会1.2递归void故事（intn）{if(n==0)return;//边界条件从前有座山；山里有座庙；庙里有个老和尚n和小和尚n；老和尚n对小和尚n说故事（n-1）；}ACM/ICPC东北地区赛事组委会1.2递归递归的概念：一个直接或间接调用自身的算法称为递归算法。一个使用函数自身给出定义的函数称为递归函数。ACM/ICPC东北地区赛事组委会1.2递归例：汉诺塔问题：输入：一个正整数表示第一个柱子上有n个盘子。输出：movetfromxtoy。ACM/ICPC东北地区赛事组委会1.2递归#includeiostreamusingnamespacestd;voidMove(intn,charx,chary){coutmovenfromxtoyendl;}voidHannoi(intn,chara,charb,charc){if(n==1)//边界条件Move(1,a,c);else{Hannoi(n-1,a,c,b);Move(n,a,c);Hannoi(n-1,b,a,c);}}ACM/ICPC东北地区赛事组委会1.2递归intmain(){intn;while(scanf(%d,&n)!=EOF){Hannoi(n,'a','b','c');}return0;}ACM/ICPC东北地区赛事组委会1.2递归写递归函数：（1）找边界条件；（2）找递推公式，或关系；ACM/ICPC东北地区赛事组委会1.2递归例：用递归函数求n！（1）边界条件：n=0时，n！=1；（2）递推公式：f（n）=n*f（n-1）；ACM/ICPC东北地区赛事组委会1.2递归Intf(intn){if(n==0)return1;elsereturnn*f(n-1);}ACM/ICPC东北地区赛事组委会1.2递归递归算法的应用举例：（1）深度优先搜索；（2）分治算法常用递归函数实现；递归函数的特点：通常递归函数书写简洁，便于读写。ACM/ICPC东北地区赛事组委会1.2递归Poj.org上的递归趣题：poj2083poj3077ACM/ICPC东北地区赛事组委会1.3枚举请你列出现在中国所有的省级行政区：ACM/ICPC东北地区赛事组委会1.3枚举假设你有，1张5元，4张2元，8张1元钱，要拿出8元可有多少种拿法？ACM/ICPC东北地区赛事组委会1.3枚举ACM/ICPC东北地区赛事组委会1.3枚举枚举算法的概念：枚举算法就是列举出问题中所有可能的解，然后根据问题的实际意义排除错误答案，最终找到正确答案的过程。ACM/ICPC东北地区赛事组委会1.3枚举输入：(有一些木棍)输入有多组，每组输入包括两行，第一行输入一个n(0=n=100),表示有n跟木棍，接着一行有n个整数(=1000)，表示木棍的长度(长度从小到大给出)。输出：输出面积最大的直角三角形的面积，且保留3位小数，如果不能组成，输出“MyGood!”。ACM/ICPC东北地区赛事组委会1.3枚举#includestdio.h#includestdlib.hintmain(){inti,j,k;doubleans;intn;intlen[110];while(scanf(%d,&n)!=EOF){for(i=1;i=n;i++)scanf(%d,&len[i]);ACM/ICPC东北地区赛事组委会1.3枚举ans=-1;for(i=1;i=n;i++){for(j=i+1;j=n;j++){for(k=j+1;k=n;k++){if(len[i]*len[i]+len[j]*len[j]==len[k]*len[k])if(0.5*len[i]*len[j]ans)ans=0.5*len[i]*len[j];}}}if(ans==-1)printf(MyGood!\n);elseprintf(%.3lf\n,ans);}}ACM/ICPC东北地区赛事组委会1.3枚举由于枚举问题解题思路是列举出问题所有的可能解，所以这种算法适用于规模不大的问题，当然，反过来在我们遇到规模不大的问题的时候就可以考虑此问题是否可用枚举法来解决。ACM/ICPC东北地区赛事组委会1.4贪心ACM/ICPC东北地区赛事组委会1.4贪心贪心的汉语释义：（1）贪得的欲望.n.（2）不知足.adj.ACM/ICPC东北地区赛事组委会1.4贪心贪心算法的概念：贪心算法是指在对问题求解时，总是做出当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做的仅是在某种意义上的局部最优解。ACM/ICPC东北地区赛事组委会1.4贪心活动安排问题：设有n个活动的集合E={1,2,3…n}，每个活动的起始结束时间分别为Si,Fi(SiFi)，每个活动都要在大礼堂举行，但是活动不能同时进行。对于i活动时间区间为[Si,Fi],j活动时间区间为[Sj,Fj]，当且仅当SjFi或SiFj时即两活动是相容的，这两个活动才可能都举办。如何选择活动，保证可进行的活动是最多的？ACM/ICPC东北地区赛事组委会1.4贪心贪心算法解决：(1)将n个活动的集合按F(即活动结束时间)的非减序列：F1=F2=…=Fn排序;(2)每次选择在未选集合中结束时间最早(即F最小)的活动，把开始时间早于(小于)最新选的活动的结束时间的那些活动标记表示不选。ACM/ICPC东北地区赛事组委会1.4贪心voidGreedy(intn,ints[],intf[],boolchose[]){chose[1]=true;intlast=1;//表示最新选择的活动的编号for(inti=2;i=n;i++){if(s[i]f[last])//i活动开始时间晚于最新选择活动结束时间{chose[i]=true;last=i;}else//说明i活动需在last未结束就开始，则不选ichose[i]=false;}}ACM/ICPC东北地区赛事组委会1.4贪心贪心可行性的证明步骤：（1）贪心选择性质；（2）最优子结构性质。ACM/ICPC东北地区赛事组委会1.4贪心贪心选择性证明(证有一个最优解以贪心选择开始，即证该最优解必包含活动1)：设E={1,2,…,n}中活动已按结束时间非减排序，A集合是E的一个最优解，A中活动也按结束时间非减排序，k是A中的第一个活动，若k=1，则A就是一个以贪心选择开始的最优解；若k1，则B=（A-{k}）U{1},由于F1=Fk,且A中活动相容，故B也是最优的。ACM/ICPC东北地区赛事组委会1.4贪心最优子结构证明(即证贪心选择后的问题将简化为一个更小的与原问题具有相同形式的子问题)：证A’=A–{1}是活动安排问题E’={i∈E:sif1}的一个最优解。事实上，如果我们能找到E’的一个解B’，它包含比A’更多的活动，那么B’U{1}包含的活动比A=A’U{1}多，那么这与A的最优性矛盾。ACM/ICPC东北地区赛事组委会1.4贪心POJ1328：在一条海岸线的一侧，有n个小岛，现在我们要在海岸线上建立雷达站，每个雷达站的信号覆盖半径为d，求我们需建立雷达站的最少个数，以使得每个小岛都可被雷达信号覆盖。(海岸线即为x轴，雷达站必须建在海岸线上，小岛的坐标为(x,y)，小岛在海岸的一侧，即y0)ACM/ICPC东北地区赛事组委会1.4贪心输入：每组数据第一行为n、d，接下来n行每行两个数x、y,表示小岛的坐标。当n、d同时为0时程序结束。输出：需建立的小岛的最少个数，若无法保证所有的小岛都被信号覆盖，就输入-1。ACM/ICPC东北地区赛事组委会1.4贪心样例输入：3212-31211202样例输出：Case1:2Case2:1ACM/ICPC东北地区赛事组委会1.4贪心ACM/ICPC东北地区赛事组委会1.4贪心#includeiostream#includealgorithm#includemath.husingnamespacestd;structIland{doubles,f;}iland[10005];intcmp(Ilanda,Ilandb){returna.fb.f;}intmain(){intn,p=1;doubled;ACM/ICPC东北地区赛事组委会1.4贪心while(scanf(%d%lf,&n,&d)!=EOF){if(n==0&&d==0)break;boolyes=true;for(inti=0;in;i++){doublex,y;scanf(%lf%lf,&x,&y);if(yd)yes=false;doublel=sqrt(d*d-y*y);iland[i].s=x-l;iland[i].f=x+l;}ACM/ICPC东北地区赛事组委会1.4贪心if(!yes){printf(Case%d:-1\n,p++);continue;}sort(iland,iland+n,cmp);intcnt=1,last=0;for(inti=1;in;i++)if(iland[i].siland[last].f){last=i;cnt++;}printf(Case%d:%d\n,p++,cnt);}}ACM/ICPC东北地区赛事组委会影片介绍：恐怖油轮ACM/ICPC东北地区赛事组委会渗透着某种算法的一部影片第一章完ACM/ICPC东北地区赛事组委会