《常用软件算法基础》课件-第章 优差生评选（分治算法）

第十四章优差生评选（分治算法）内容目标：分治算法基本概念优差生评选二分法实现最大子段二分不独立算法实现第k小元素非等分分治算法实现重难点：各种分治算法设计思想以及应用实现1.功能模块在一个班中有n个学生参加语文考试，请通过计算找出语文成绩最优和最差的学生。2.1分治算法基本概念定义：分治法（DivideandConquer）的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的几个相似问题，以便各个击破，分而治之。算法设计思想分治法求解问题的过程是，将整个问题分解成若干个小问题后分而治之，若果分解得到的自问题相对来说还太大，则可以反复使用分治策略将这些子问题分成更小的同类型子问题，直至产生出方便求解的子问题，必要时逐步合并这些子问题的解，从而得到问题的解。分治法的基本步骤在每个递归层上有3个步骤。分解：将原问题分解为若干个规模较小，相互独立，与问题形式相同的子问题；解决：若子问题规模较小而容易被解决则直接解，否则再继续分解为更小的子问题，直到容易解决；合并：将已求解的各个子问题的解，逐步合并为原问题的解。有时问题分解后，不必求解所有的子问题，也就不必作第三步的操作。例如折半查找，在判别出问题的解在某一个子问题中后，其他的子问题就不必求解了，问题的解就是最后（最小）的子问题的解。分治法的这类应用，又称为“减治法”。2.2分治算法基本概念适合用分治法策略问题：当求解一个输入规模为n且取值又相当大的问题时，用蛮力策略效率一般得不到保证。若问题能满足以下几个条件，就能用分治法来提高解决问题的效率。（1）能将这n个数据分解成k个不同子集合，且得到k个子集合是可以独立求解的子问题，其中；（2）分解所得到的子问题与原问题具有相似的结构，便于利用递归或循环机制；（3）在求出这些子问题的解之后，就可以退出原问题的解。2.3分治算法基本概念算法框架：Dvide-and-Conquer(n)//n为问题规模

{if(n<=n0)//n0为可解子问题的规模{解子问题；

return（子问题的解）；}for（i=1；i<=k；i=i+1）//分解为较小的k个子问题P1，P2，…，Pk {分解原问题为更小的子问题Pi；

yi=Divide-and-Conquer(|Pi|);}//递归解决Pi，|Pi|为Pi的规模

T=MERGE(y1,y2,...,yk)

;//合并子问题return(T)

;}

其中|P|表示问题P的规模；n0为一阈值，表示当问题P的规模不超过n0时，问题已容易直接解出，不必再继续分解。算法MERGE(y1,y2,...,yk)

是该分治法中的合并子集算法，用于将P的子问题P1，P2，...，Pk的相应的解y1,y2,...,yk合并为P的解。在一些问题中不需要这一步。如折半查找、二叉排序树查找等算法。3.1业务实现---优差生评选二分法：在采用分治算法时，一个问题每次分解成的子问题个数一般是固定的，每个问题的规模也是平均分配的。当每次都将问题分解为原问题规模的一半时，称为二分法。二分法是分治法较常用的分解方法，数据结构中的折半查找，是采用此算法实现的。优差生评选算法分析：本问题如果用循环法进行求解，要循环n次，并作2n次比较可以找到最大和最小的学生成绩。这里用二分法解决该问题，比较次数较少，主要思想如下：（1）将数据等分成两组（两组数据可能差1），目的是分别求取其中的最大（小）值。（2）递归分解直到每组元素的个数<=2，可以简单找到最大（小）值。（3）回溯时合并问题的解，在两个子问题的解中大者取大，小者取小，即合并当前问题的解3.2业务实现---优差生评选最大最小值对象类在进行递归调用时，将最优和最差学生成绩用一个对象进行返回。publicclassFz_Max{ publicdoublemax; publicdoubleMin;

publicFz_Max(doublea,doubleb) { max=a; Min=b; }}

3.3业务实现---优差生评选二分法求解最优最差学生的代码实现：publicFz_MaxMaxmin(inti,intj){//典型二分求解最大最小值问题

intmid;//局部变量求中值

Fz_Maxjg=newFz_Max(0.0,0.0); Fz_Maxleft=newFz_Max(0.0,0.0); Fz_MaxRight=newFz_Max(0.0,0.0); //局部变量记录子问题的最大最小值

if(i==j) //若子问题规模为1个元素时直接得解

{ jg.max=a.base_info[i].st_yw; jg.Min=a.base_info[i].st_yw; } elseif(i==j-1) //若子问题为两个元素时直接求解 if(a.base_info[i].st_yw<a.base_info[j].st_yw) { jg.max=a.base_info[j].st_yw; jg.Min=a.base_info[i].st_yw; }else { jg.max=a.base_info[i].st_yw; jg.Min=a.base_info[j].st_yw; }3.4业务实现---优差生评选二分法求解最优最差学生的代码实现： else//若子问题为多个元素时

{ mid=(i+j)/2;//求取中间元素位置

left=Maxmin(i,mid);//递归求左子问题的解

Right=Maxmin(mid+1,j);//递归求右子问题的解

if(left.max>Right.max)//合并子问题的解

jg.max=left.max; else jg.max=Right.max; if(left.Min>Right.Min) jg.Min=Right.Min; else jg.Min=left.Min; } returnjg;}

4.1知识扩展---最大子段问题4.1知识扩展---最大子段问题问题描述：求数列的最大子段和。给定n个元素的整数列（可能为负整数）a1，a2，…，an。求形如：ai，ai+1，…，ajij=1，…，ni<=j的子段，使其和为最大。当所有整数均为负数时定义其最大子段和为0。例如，当（a1，a2，a3，a4，a5，a6）=（-2，11，-4，13，-5，-2）时，最大子段和为：i=2，j=4（下表从1开始）。4.2知识扩展---最大子段问题问题分析：用二分法将实例中的数据分解为两组（-2，11，-4），（13，-5，-2），第一组子问题的解是11，第2组子问题的解是13，两个子问题的解不能简单地得到原问题的解。由此可以看出这个问题不能用二分法分解成独立的两个子问题，子问题中还有公共的子问题。这类问题称为子问题重叠类的问题。 分解方法和上例一样采用二分法，虽然分解后的问题不独立，但通过对重叠子问题进行专门处理，并对所有子问题合并进行设计，就可以用二分策略解决此问题。 如果将所给的序列a[1:n]分为长度相等的两段a[1:n/2]和a[(n/2)+1:n]，分别求出这两段的最大子段和，则a[1:n]的最大子段和有3种情形：情形（1）a[1:n]的最大子段和与a[1:（n/2）]的最大子段和相同。情形（2）a[1:n]的最大子段和与a[(n/2)+1:n]的最大子段和相同。情形（3）a[1:n]的最大子段和为a[i:j]，且1<=i<=(n/2),(n+1)/2<=j<=n。情形（1）和情形（2）可递归求得。对于情形（3），序列中的元素a[(n/2)]与a[(n/2)+1]一定在最大子段中。因此，可以计算出a[i:(n/2)]的最大值s1；并计算出a[(n/2)+1:j]中的最大值s2。则s1+s2即为出现情况（3）时的最优值。4.3知识扩展---最大子段问题代码实现：publicintmax_sub_sum(int[]a,intleft,intright){//求最大子段问题，a是数组，left左边界，right右边界

intcenter,i,j,sum,left_sum,right_sum,s1,s2,lefts,rights if(left==right) {//当子段子段只有一个元素时，直接得到结果

if(a[left]>0) returna[left]; else return0; } else {//将子段分解成左右两个子段

center=(left+right)/2; left_sum=max_sub_sum(a,left,center);//求左子段最大子段

right_sum=max_sub_sum(a,center+1,right);//求右子段最大子段

s1=0; lefts=0; 4.4知识扩展---最大子段问题代码实现： for(i=center;i>=left;i--)//若最大子段包含中间元素中点向前求子段

{ lefts=lefts+a[i]; if(lefts>s1) s1=lefts; } s2=0; rights=0; for(i=center+1;i<=right;i++)//若最大子段包含中间元素，从中点向后求子段

{ rights=rights+a[i]; if(rights>s2) s2=rights; } if((s1+s2)<left_sum&&right_sum<left_sum)//若最大子段只在左子段

returnleft_sum; if((s1+s2)<right_sum)//若最大子段在右子段

returnright_sum; returns1+s2; //若最大子段包含中间元素

} }

5.1知识扩展---第k小元素问题描述：对于给定一个n个元素的数组a【0，n-1】要求从中寻找该数组的第k小元素。5.2知识扩展---第k小元素问题分析： 本问题不能用二分法分解成独立的子问题，一种通用的设计策略是蛮力法，本题可以通过对全部数据进行排序后，得到问题的解。即使用较好的排序方法，算法的复杂度为O（nlongn）。 说到排序，快速排序算法其实也属于分治策略的应用，不过不是对问题进行等份分解的（二分法），而是通过分界数据（支点）将问题分解成独立的子问题。由于该题要借用此算法，在此先回顾一下快速排序算法。 首先选第一个数作为分界数据，将比它小的数据存放在它的左边，将比它大的数据存放在它的右边，它存放在左、右两个子集之间。这样左、右子集就是问题分解后的独立子问题，再用同样的方法，继续解决这些子问题，直到每个子集只有一个数据，自然就排好序了，也就完成了全部数据的排序工作。 这里通过改写快速排序算法，来解决问题。记一趟排序后，分解出左子集中的元素个数为nleft，则选择问题，可能有以下几种情形之一：

(1)nleft=k-1，则分解数解释选择问题的答案。（2）nleft>k-1，则选择问题的答案继续在左子集中找，问题规模变小了。（3）nleft<k-1,则选择问题的答案继续在右子集中找，问题变为选择第k-nleft-1小的数，问题的规模也变小了。5.3知识扩展---第k小元素代码实现：publicintxz(int[]a,intn,intk){ if(k<1||k>n) return-1;//错误

returnselect(a,0,n-1,k);//调用函数，寻找第k小元素}5.4知识扩展---第k小元素代码实现：publicvoidSwap(refintx,refinty){ intt; t=x; x=y; y=t;}

5.5知识扩展---第k小元素代码实现：publicintselect(int[]a,intleft,intrigh