《NOIP基础算法——贪心和分治》由会员分享，可在线阅读，更多相关《NOIP基础算法——贪心和分治（114页珍藏版）》请在金锄头文库上搜索。
1、单击此处编辑母版标题样式 单击此处编辑母版副标题样式 *1 NOIP基础算法分治与贪心 一个人拥有健康，美貌，诚信，机敏，才学，金钱，荣誉，7个背囊，渡船开始时风平浪静，可是不久就刮起了大风，船夫说要扔掉一个背囊，你会扔掉那个背囊呢？最后你要扔掉哪一个？为什么呢?说说你的理由。 第五部分第五部分 分治策略分治策略 一个人拥有健康，美貌，诚信，机敏，才学，金钱，荣誉，7个背囊，渡船开始时风平浪静，可是不久就刮起了大风，船夫说要扔掉一个背囊，你会扔掉那个背囊呢？最后你要扔掉哪一个？为什么呢?说说你的理由。 一、分治思想 n 分治法，又叫分治策略，顾名思义，分而治之分而治之。 n 它的基本思想：对于
2、难以直接解决的规模较大的 问题，把它分解成若干个能直接解决的相互独立 的子问题，递归求出各子问题的解，再合并子问 题的解，得到原问题的解。 n 通过减少问题的规模，逐步求解，能够明显降低 解决问题的复杂度。 一个人拥有健康，美貌，诚信，机敏，才学，金钱，荣誉，7个背囊，渡船开始时风平浪静，可是不久就刮起了大风，船夫说要扔掉一个背囊，你会扔掉那个背囊呢？最后你要扔掉哪一个？为什么呢?说说你的理由。 二、分治法的适用条件 n 能使用分治法解决的问题，它们一般具备以下几个特征： 该问题可分解成若干相互独立、规模较小的相同子问题； 子问题缩小到一定的程度就能轻易得到解； 子问题的解合并后，能得到原问题
3、的解； n 分治法在信息学竞赛中应用非常广泛，使用分治策略能生成 一些常用的算法和数据结构，如快排、最优二叉树、线段树 等；还可以直接使用分治策略，解决一些规模很大、无法直 接下手的问题。 一个人拥有健康，美貌，诚信，机敏，才学，金钱，荣誉，7个背囊，渡船开始时风平浪静，可是不久就刮起了大风，船夫说要扔掉一个背囊，你会扔掉那个背囊呢？最后你要扔掉哪一个？为什么呢?说说你的理由。 三、分治的三步骤 n分解：将要解决的问题分解成若干个规 模较小的同类子问题； n解决：当子问题划分得足够小时，求解 出子问题的解。 n合并：将子问题的解逐层合并成原问题 的解。 一个人拥有健康，美貌，诚信，机敏，才学，
4、金钱，荣誉，7个背囊，渡船开始时风平浪静，可是不久就刮起了大风，船夫说要扔掉一个背囊，你会扔掉那个背囊呢？最后你要扔掉哪一个？为什么呢?说说你的理由。 分治算法设计过程图 一个人拥有健康，美貌，诚信，机敏，才学，金钱，荣誉，7个背囊，渡船开始时风平浪静，可是不久就刮起了大风，船夫说要扔掉一个背囊，你会扔掉那个背囊呢？最后你要扔掉哪一个？为什么呢?说说你的理由。 n 在划分问题时，可以采用递归策略，把一个大问题逐 步分解成规模较小的子问题，直至可以直接求出子问 题的解；再将子问题逐层合并，返回到顶层，得到原 问题的解。 n 根据分治策略的划分原则，把原问题划分成多少个子 问题才合适呢？各个子问题
5、的规模应该多大才合适呢 ？ n 一般来说，每次划分成2个子问题，每个子问题的规 模差不多最合适。合并解时要因题而异，有些问题递 归分解完能直接得到原问题的解，有些问题需逐层合 并，得到原问题的解。 一个人拥有健康，美貌，诚信，机敏，才学，金钱，荣誉，7个背囊，渡船开始时风平浪静，可是不久就刮起了大风，船夫说要扔掉一个背囊，你会扔掉那个背囊呢？最后你要扔掉哪一个？为什么呢?说说你的理由。 四、分治的框架结构 procedure Divide() begin if(问题不可分)then/解决 begin 直接求解； 返回问题的解； end else begin 对原问题进行分治；/分解 递归对每一
6、个分治的部分进行求解; /解决 归并整个问题，得出全问题的解; /合并 end end; 一个人拥有健康，美貌，诚信，机敏，才学，金钱，荣誉，7个背囊，渡船开始时风平浪静，可是不久就刮起了大风，船夫说要扔掉一个背囊，你会扔掉那个背囊呢？最后你要扔掉哪一个？为什么呢?说说你的理由。 五、分治的典型应用五、分治的典型应用 n n 1 1、求最大值和最小值、求最大值和最小值 n n 2 2、求方程的根、求方程的根 n n 3 3、二分查找、二分查找 n n 4 4、归并排序、归并排序 n n 5 5、快速幂、快速幂 n n 6 6、求解线性递推关系、求解线性递推关系 n n 7 7、棋盘覆盖问题、棋
7、盘覆盖问题 n n 8 8、循环日程表问题、循环日程表问题 n n 9 9、寻找最近点对、寻找最近点对 一个人拥有健康，美貌，诚信，机敏，才学，金钱，荣誉，7个背囊，渡船开始时风平浪静，可是不久就刮起了大风，船夫说要扔掉一个背囊，你会扔掉那个背囊呢？最后你要扔掉哪一个？为什么呢?说说你的理由。 1 1、求最大值和最小值、求最大值和最小值 n 例题1：给n个数，求它们之中最大值和最小值，要求比较 次数尽量小。 分析：假设数据个数为n,存放在数组a1.n中。可以直接进 行比较： minn:=a1;maxx:=a1; for i:=2 to n do if aimaxx then maxx:=ai;
8、 else if aixr1 then begin maxx:=xr2;minn:=xr1;end else begin maxx:=xr1;minn:=xr2;end end else begin d:=(r1+r2)/2; pd(r1,d,max1,min1); pd(d+1,r2,max2,min2); if max1max2 then maxx:=max1;else maxx:=max2; if min1=1。要求由小到大依次在同一行输出这三个 实根(根与根之间留有空格)，并精确到小数点后4位。 【文件输入】输入仅一行，有四个数，依次为a、b、c、d 【文件输出】输出也只有一行，即三个
9、根(从小到大输出) 【样例输入】1 -5 -4 20 【样例输入】-2.00 2.00 5.00 一个人拥有健康，美貌，诚信，机敏，才学，金钱，荣誉，7个背囊，渡船开始时风平浪静，可是不久就刮起了大风，船夫说要扔掉一个背囊，你会扔掉那个背囊呢？最后你要扔掉哪一个？为什么呢?说说你的理由。 分析分析 n 如果精确到小数点后两位，可用简单枚举法：将x从-100.00 到100.00（步长0.01）逐一枚举，得到20000个 f(x)，取其值与0最 接近的三个f(x)，对应的x即为答案。而题目已改成精度为 小数点后4位，枚举算法时间复杂度将达不到要求。 n 直接使用求根公式，极为复杂。加上本题的提示
10、给我们以 启迪：采用二分法逐渐缩小根的范围，从而得到根的某精 度的数值。 一个人拥有健康，美貌，诚信，机敏，才学，金钱，荣誉，7个背囊，渡船开始时风平浪静，可是不久就刮起了大风，船夫说要扔掉一个背囊，你会扔掉那个背囊呢？最后你要扔掉哪一个？为什么呢?说说你的理由。 分析分析 n A.当已知区间(a,b)内有一个根时； n 用二分法求根，若区间(a,b)内有根，则必有f(a)*f(b)b或f(a+b)/2)=0，则可确定根为(a+b)/2并退出过程 ； 、若f(a)*f(a+b)/2)0,则必然有f(a+b)/2)*f(b)=1。因此可知：在-100,-99、-99,-98、99，100、100
11、，100 这201个区间内，每个区间内至多只能有一个根。即：除区 间100，100外，其余区间a,a+1，只有当f(a)=0或f(a)*f(a+1)0时， 方程在此区间内才有解。若f(a)=0 ，解即为a；若f(a)*f(a+1)0 ， 则可以利用A中所述的二分法迅速出找出解。如此可求出 方程的所有的解。 一个人拥有健康，美貌，诚信，机敏，才学，金钱，荣誉，7个背囊，渡船开始时风平浪静，可是不久就刮起了大风，船夫说要扔掉一个背囊，你会扔掉那个背囊呢？最后你要扔掉哪一个？为什么呢?说说你的理由。 核心参考代码核心参考代码 procedure Divide(x1,x2:double) Begin
12、var x0,y0,y1,y2:double; x0:=(x1+x2)div 2; y1:=cal(x1);y2:=cal(x2);y0:=cal(x0); if(x2-x10.00001 and y1*y20)then begin write(x2+x1)div 2:0:4);exit;end if(y1*y01)then divide(x1,x0); if(y0*y21)then divide(x0,x2); End; 一个人拥有健康，美貌，诚信，机敏，才学，金钱，荣誉，7个背囊，渡船开始时风平浪静，可是不久就刮起了大风，船夫说要扔掉一个背囊，你会扔掉那个背囊呢？最后你要扔掉哪一个？为什么
13、呢?说说你的理由。 3 3、归并排序、归并排序 n 归并排序的基本思想：归并排序充分应用分治算法的策略 ，通过二分的思想，将n个数最终分成n个单独的有序数列 ，每个数列中仅有一个数字；再将相邻的两列数据合并成 一个有序数列；再重复上面的合并操作，直到合成一个有 序数列。按照分治三步法来说： （1）划分：把序列分成元素个数相等的两半； （2）递归求解：把两半分别排序； （3）合并：把两个有序表合成一个有序表； 一个人拥有健康，美貌，诚信，机敏，才学，金钱，荣誉，7个背囊，渡船开始时风平浪静，可是不久就刮起了大风，船夫说要扔掉一个背囊，你会扔掉那个背囊呢？最后你要扔掉哪一个？为什么呢?说说你的理由
14、。 一个人拥有健康，美貌，诚信，机敏，才学，金钱，荣誉，7个背囊，渡船开始时风平浪静，可是不久就刮起了大风，船夫说要扔掉一个背囊，你会扔掉那个背囊呢？最后你要扔掉哪一个？为什么呢?说说你的理由。 分析 n 显然，前两部分是很容易完成的，关键在于如何把两个有 序表合成一个。每次只需要把两个有序表中当前的最小元 素加以比较，删除较小元素并加入合并后的新表中。 一个人拥有健康，美貌，诚信，机敏，才学，金钱，荣誉，7个背囊，渡船开始时风平浪静，可是不久就刮起了大风，船夫说要扔掉一个背囊，你会扔掉那个背囊呢？最后你要扔掉哪一个？为什么呢?说说你的理由。 核心参考代码核心参考代码 procedure Me
15、rgeSort(left,right:integer)/归并排序 begin if left=right then exit; /只有一个元素 mid:=(left+right)div 2; /找中间位 MergeSort(left,mid); /对左边归并 MergeSort(mid+1,right); /对右边归并 i:=left;j:=mid+1,p:=left; /合并左右 while(i=mid and jaj)then begin tempp:=aj;inc(p);inc(j);end else begin tempp:=ai;inc(p);inc(i);end while(i=mid)do begin tempp:=ai;inc(p);inc(i);end while(j=right)do begin tempp:=aj;inc(p);inc(i);end for i:=left t
