算法设计与分析 思政课件 第4章 分治法

第4章分治法4.1分治法概述4.2求解排列问题CONTENTS提纲4.3求解查找问题4.5求xn和An问题4.4求解组合问题1/61分治从字面上的解释就是“分而治之”。把一个复杂的问题分成k（1<k≤n）个相同或相似的子问题，再把子问题分成更小的子问题，以此类推，直到可以直接求解为止，原问题的解可以通过子问题的解合并得到。4.1.1什么是分治法4.1分治法概述2/61分治法求解问题的特征问题的规模缩小到一定程度就可以容易地解决。问题可以分解为若干个规模较小的相似问题

基本前提。利用子问题的解可以合并为问题的解

关键。问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题

分治法效率。3/61分治算法的求解过程子问题1的解原问题子问题1子问题2子问题k…分子问题2的解子问题k的解治原问题的解合并4/61Tdivide-and-conquer(P) //分治算法框架{if|P|≤n0returnadhoc(P);

将P分解为较小的子问题P1，P2，…，Pk;for(i=1;i<=k;i++) //循环处理k次yi=divide-and-conquer(Pi); //递归解决Pireturnmerge(y1，y2，…，yk); //合并子问题}4.1.2分治算法框架5/61【例4-1】给定一棵采用二叉链存储的二叉树b，设计一个算法求其中叶子结点的个数。解设f(b)用于求二叉树b中叶子结点的个数bf(b->left)f(b)f(b->right)f(b)=0 当b=NULLf(b)=1 当b为叶子结点f(b)=f(b->left)+f(b->right) 其他6/61intleafnodes(TreeNode*b){ if(b==NULL) //空树 return0; if(b->left==NULL&&b->right==NULL) return1; //只有一个叶子结点 else //其他情况 returnleafnodes(b->left)+leafnodes(b->right);}7/614.2.1快速排序4.2求解排列问题R[s]R[s+1]…

R[t]无序区一次划分R[s]…

R[i-1]R[i+1]…

R[t]无序区1无序区2R[i]归位所有元素≥basebase所有元素≤basebase8/61分解：将原序列R[s..t]分解成两个子序列R[s..i-1]和R[i+1..t]，其中i为划分的基准位置。即将整个问题分解为两个子问题。求解子问题：若子序列的长度为0或为1，则它是有序的，直接返回；否则递归地求解各个子问题。合并：由于每个子问题的排序结果直接存放在数组a中，合并步骤不需要执行任何操作。快速排序的分治策略9/612517106943812571069438345691078436910788791078①②③④⑤⑥10/61划分算法设计1）移动法intPartition1(vector<int>&R,ints,intt) //划分算法1{ inti=s,j=t; intbase=R[s]; //以表首元素为基准 while(i<j) //从两端交替向中间遍历直至i=j { while(j>i&&R[j]>=base)j--; //从后向前找一个小于基准的R[j] if(j>i) { R[i]=R[j]; //R[j]前移覆盖R[i] i++; } while(i<j&&R[i]<=base)i++; //从前向后找一个大于基准的R[i] if(i<j) { R[j]=R[i]; //R[i]后移覆盖R[j] j--; } } R[i]=base; //基准归位 returni; //返回基准归位的位置}11/612）区间划分法>base元素区间Rs…RiRi+1…RtRj≤base时交换Rj…j≤base元素区间base>base元素区间Rs…RiRi+1…RtRj…≤base元素区间base交换12/612）区间划分法intPartition2(vector<int>&R,ints,intt) //划分算法2{ inti=s,j=s+1; intbase=R[s]; //以首元素为基准 while(j<=t) //j从s+1开始遍历其他元素 { if(R[j]<=base) //找到小于等于基准的元素R[j] { i++; //扩大≤base的元素区间 if(i!=j) swap(R[i],R[j]); //将R[i]与R[j]交换 } j++; //继续扫描 } swap(R[s],R[i]); //将基准R[s]和R[i]进行交换 returni;}13/61快速排序算法设计递归模型f(R，s，t)≡不做任何事情

R[s..t]为空或仅有一个元素时f(R，s，t)≡i=Partition1(R，s，t); 其他情况（也可以调用Partition2）f(R，s，i-1);f(R，i+1，t);R[s]R[s+1]…

R[t]无序区一趟划分R[s]…

R[i-1]R[i+1]…

R[t]无序区1无序区2R[i]归位所有元素≥basebase所有元素≤basebase14/61voidQuickSort11(vector<int>&R,ints,intt) //被QuickSort1调用{ if(s<t) //至少存在两个元素 { inti=Partition1(R,s,t); //可用前面两种划分算法

QuickSort11(R,s,i-1); //对无序列1递归排序

QuickSort11(R,i+1,t); //对子序列2递归排序 }}voidQuickSort1(vector<int>&R) //递归算法：R[0..n-1]快速排序{ intn=R.size();

QuickSort11(R,0,n-1);}平均时间复杂度也是O(nlog2n)。STL的sort()算法采用快速排序实现。15/614.2.2查找一个序列中第k小元素给定含n（n>1）整数的无序序列，求这个序列中第k（1≤k≤n）小的元素（不是第k个不同的元素，而是递增排序后序号为k-1的元素）。例如，a=（1，1，2，3，5，5），k=2时结果为1。16/61

i=4，k-1<i

i=1，k-1>i251431254353434

i=2，k-1=i解k=317/61intQuickSelect11(vector<int>&R,ints,intt,intk) //被QuickSelect调用{ if(s<t) //至少存在2个元素 { inti=Partition1(R,s,t); //划分算法 if(k-1==i) returnR[i]; elseif(k-1<i) returnQuickSelect11(R,s,i-1,k); //在左子序列中递归查找 else returnQuickSelect11(R,i+1,t,k); //在右子序列中递归查找 } elseif(s==t&&s==k-1) //只有一个元素且s=k-1 returnR[k-1];}intQuickSelect1(vector<int>&R,intk) //递归算法：找第k小的元素{ intn=R.size(); returnQuickSelect11(R,0,n-1,k);}时间复杂度为O(n)。18/61已知由n（n≥2）个正整数构成的集合A={ak}（0≤k<n），将其划分为两个不相交的子集A1和A2，元素个数分别是n1和n2，A1和A2中元素之和分别为S1和S2。设计一个尽可能高效的划分算法，满足|n1-n2|最小且|S1-S2|最大。要求：（1）给出算法的基本设计思想。（2）根据设计思想，采用C、C++描述算法，关键之处给出注释。（3）说明你所设计算法的时间复杂度和空间复杂度。2016年全国计算机学科专业考研题示例19/61查找第n/2小的元素递归快速排序将A递增排序，前

n/2个元素放在A1中，其他放在A2中将最小的

n/2个元素放在A1中，其他放在A2中20/61解intPartition(inta[],intlow,inthigh) //以a[low]为基准划分{ inti=low,j=high; intpovit=a[low]; while(i<j) { while(i<j&&a[j]>=povit)j--; if((i<j) { a[i]=a[j]; i++; } while(i<j&&a[i]<=povit)i++; if(i<j) { a[j]=a[i]; j--; } } a[i]=povit; returni;}21/61intSolution(inta[],intn) //求解{ intlow=0,high=n-1; boolflag=true; while(flag) { inti=Partition(a,low,high); if(i==n/2-1) //基准a[i]为第n/2小的元素

flag=false; elseif(n/2-1>i) //在右区间查找

low=i+1; else high=i-1; //在左区间查找

} ints1=0,s2=0; for(inti=0;i<n/2;i++) s1+=a[i]; for(intj=n/2;j<n;j++) s2+=a[j]; returns2-s1;}时间复杂度为O(n)22/614.2.3归并排序1.自底向上的二路归并排序（迭代）n=10排序趟数为

log2n

=4[2][5][1][7][10]][6][9][4][3][8][25][17][6[0][49][38][1257][46910][38][124567910][38][12345678910]底23/61分治策略：分解：将原序列分解成length长度的若干子序列。求解子问题：将相邻的两个子序列调用Merge算法合并成一个有序子序列。合并：由于每个子问题的排序结果直接存放在R中，合并步骤不需要执行任何操作。

24/61R[low..mid]和R[mid+1..high]是两个相邻的有序子序列（有序段），将其所有元素归并为有序子序列R[low..high]。voidMerge(vector<int>&R,intlow,intmid,inthigh){ vector<int>R1; //用做临时表 inti=low,j=mid+1; //i、j分别为两个子表的下标 while(i<=mid&&j<=high) //在子表1和子表2均未遍历完时循环 { if(R[i]<=R[j]) //将子表1中的元素归并到R1 { R1.push_back(R[i]); i++; } else //将子表2中的元素归并到R1 { R1.push_back(R[j]); j++; }}25/61 while(i<=mid) //将子表1余下元素改变到R1 { R1.push_back(R[i]); i++; } while(j<=high) //将子表2余下元素改变到R1 { R1.push_back(R[j]); j++;; } for(intk=0,i=low;i<=high;k++,i++) //将R1复制回R中 R[i]=R1[k];}时间复杂度为O(m)。26/61voidMergePass(vector<int>&R,intlength) //一趟二路归并排序{ inti,n=R.size(); for(i=0;i+2*length-1<n;i=i+2*length) //两两归并相邻长度为length的子序列

Merge(R,i,i+length-1,i+2*length-1); if(i+length<n) //归并余下最后两个子表

Merge(R,i,i+length-1,n-1);}时间复杂度为O(n)。27/61voidMergeSort1(vector<int>&R) //自底向上的二路归并算法{ for(intlength=1;length<R.size();length=2*length)

MergePass(R,length);}时间复杂度为O(nlog2n)。28/612.自顶向下的二路归并排序（递归）251710694382517106943825171025125

2512571071012571069438694696946938383468912345678910顶29/61voidMergeSort21(vector<int>&R,intlow,inthigh) //被MergeSort2调用{ if(low<high) //子序列有两个或以上元素 { intmid=(low+high)/2; //取中间位置

MergeSort21(R,low,mid); //对R[low..mid]排序

MergeSort21(R,mid+1,high); //对R[mid+1..high]排序

Merge(R,low,mid,high); //将两有序子序列合并 }}voidMergeSort2(vector<int>&R) //自顶向下的二路归并算法{ intn=R.size();

MergeSort21(R,0,n-1);}时间复杂度为O(nlog2n)。30/614.2.4实战—求逆序数（POJ2299）问题描述：给定一组无序的整数序列，每次只能交换相邻的两个元素，求最少交换几次才能使序列递增有序。输入格式：输入包含几个测试用例。每个测试用例均以包含单个整数n<500,000（输入序列的长度）的一行开头，接下来是n个以单个空格分隔整数（0≤整数值≤999,999,999）。输入以n=0结束，不必处理此序列。输出格式：对于每个测试用例，输出一行包含整数op，op是对给定输入序列进行排序所需的最小交换操作数。例如：a=（9，1，0，5，4），结果为64101031/61二路归并排序：在合并过程中求逆序数。解若a[i]>a[j]（归并a[j]），看出前半部分中a[i..mid]都比a[j]大，对应的逆序对个数为mid-i+1。②若a[i]≤a[j]（归并a[i]），不产生逆序对。a[low]…a[i]…a[mid]a[i]>a[j]a[mid+1]…a[j]…a[high]a[i..mid]>a[j]

有逆序对(a[i]，a[j])，(a[i+1]，a[j])，…，(a[mid]，a[j])，共mid-i+1个有序段1有序段232/61#include<iostream>#include<vector>usingnamespacestd;longlongans; //存放逆序数voidMerge(vector<int>&R,intlow,intmid,inthigh)//将R[low..mid]和R[mid+1..high]两个有序段二路归并为一个有序段R[low..high]{ vector<int>R1; R1.resize(high-low+1); //设置R1的长度为high-low+1 inti=low,j=mid+1,k=0; //k是R1的下标,i、j分别为第1、2段的下标 while(i<=mid&&j<=high) //在第1段和第2段均未扫描完时循环 { if(R[i]>R[j]) //将第2段中的元素放入R1中 { R1[k]=R[j];

ans+=mid-i+1;

//累计逆序数 j++;k++; } else //将第1段中的元素放入R1中 { R1[k]=R[i]; i++;k++; }}33/61 while(i<=mid) //将第1段余下部分复制到R1 { R1[k]=R[i]; i++;k++; } while(j<=high) //将第2段余下部分复制到R1 { R1[k]=R[j]; j++;k++; } for(k=0,i=low;i<=high;k++,i++) //将R1复制回R中 R[i]=R1[k];}34/61voidMergeSort21(vector<int>&R,ints,intt) //被MergeSort2调用{ if(s>=t)return; //R[s..t]的长度为0或者1时返回 intm=(s+t)/2; //取中间位置m

MergeSort21(R,s,m); //对前子表排序

MergeSort21(R,m+1,t); //对后子表排序

Merge(R,s,m,t); //将两个有序子表合并成一个有序表}voidMergeSort2(vector<int>&R,intn) //自顶向下的二路归并排序{

MergeSort21(R,0,n-1);}35/61intmain(){ intn,x; while(scanf("%d",&n)!=EOF) { if(n==0)break; vector<int>R; for(inti=0;i<n;i++) { scanf("%d",&x); R.push_back(x); } ans=0;

MergeSort2(R,n); printf("%lld\n",ans); } return0;}36/614.3.1查找最大和次大元素4.3求解查找问题对于给定的含有n个整数的无序序列，求这个序列中最大和次大的两个不同的元素。例如：

a=（1，3），max1=3，max2=1。

a=（1，3，3），max1=3，max2=3。

a=（1），max1=3，max2=-∞。37/61分治法求最大元素max1和次大元素max2的过程如下：若a[low.high]中只有一个元素，则max1=a[low]，max2=-INF（-∞）。若a[low.high]中只有两个元素，则max1=max(a[low]，a[high])，max2=min(a[low]，a[high])。若a[low.high]中只有两个以上元素，按中间位置mid=(low+high)/2划分为a[low..mid]和a[mid+1..high]左右两个区间（注意左区间包含a[mid]元素）。递归求出左区间最大元素lmax1和次大元素lmax2；递归求出右区间最大元素rmax1和次大元素rmax2。合并：若lmax1>rmax1，则max1=lmax1，max2=max(lmax2，rmax1)，否则max1=rmax1，max2=max(lmax1，rmax2)。解38/61voidsolve1(vector<int>&a,intlow,inthigh,int&max1,int&max2)//被solve调用{ if(low==high) //区间只有一个元素 { max1=a[low];max2=-INF;} elseif(low==high-1) //区间只有两个元素 { max1=max(a[low],a[high]); max2=min(a[low],a[high]); } else { intmid=(low+high)/2;intlmax1,lmax2;intrmax1,rmax2;

solve1(a,low,mid,lmax1,lmax2); //左区间求lmax1和lmax2 solve1(a,mid+1,high,rmax1,rmax2); //右区间求lmax1和lmax2 if(lmax1>rmax1) { max1=lmax1; max2=max(lmax2,rmax1); //lmax2,rmax1中求次大元素 } else { max1=rmax1; max2=max(lmax1,rmax2); //lmax1,rmax2中求次大元素 } }}39/61voidsolve(vector<int>&a,int&max1,int&max2)//求a中最大和次大元素{

solve1(a,0,a.size()-1,max1,max2);}时间复杂度为O(n)。40/614.3.2二分查找intBinSearch11(vector<int>&R,intlow,inthigh,intk)//被BinSearch1调用{ if(low<=high) //当前区间存在元素时 { intmid=(low+high)/2; //求查找区间的中间位置 if(k==R[mid]) //找到后返回下标mid returnmid; if(k<R[mid]) //在左区间中递归查找 returnBinSearch11(R,low,mid-1,k); else //在右区间中递归查找 returnBinSearch11(R,mid+1,high,k); } elsereturn-1; //若当前查找区间为空时返回-1}intBinSearch1(vector<int>&R,intk) //递归算法：二分查找{ intn=R.size(); returnBinSearch11(R,0,n-1,k);}R递增有序，查找k的序号41/61循环不变式：若k存在于R[0..n-1]，那么它一定在查找区间R[low..high]中。初始化：循环开始之前查找区间R[low..high]就是R[0..n-1]，显然成立。保持：每轮循环开始前，k存在于查找区间R[low..high]中，每轮循环是先计算mid=(low+high)/2，操作如下：①k=R[mid]，查找到了值为k的元素，直接返回其序号mid。②k<R[mid]，值为k的元素只可能存在于R[low..mid-1]中。③k>R[mid]，值为k的元素只可能存在于R[mid+1..high]中。每次减小查找区间长度，最后由1（low=high）变为0（low>high）。终止：循环结束时low>high成立，查找区间为空，表示k不存在于所有步骤的查找区间中，再结合每一步排除的部分元素中也不可能有k，因此k不存在于R中。二分查找算法的正确性证明42/61intBinSearch2(vector<int>&R,intk) //迭代算法：二分查找{ intlow=0,high=R.size()-1; while(low<=high) //当前区间存在元素时循环 { intmid=(low+high)/2; //求查找区间的中间位置 if(k==R[mid]) //找到后返回其下标mid returnmid; if(k<R[mid]) //在左区间中递归查找 high=mid-1; else //在右区间中递归查找 low=mid+1; } return-1; //若当前查找区间为空时返回-1}R递增有序，查找k的序号43/61【例4-2】对于含n个元素的递增有序序列R，其中元素可能重复出现。设计一个高效算法查找k的插入点，k的插入点是指有序插入k的第一个位置，或者说R中第一个大于等于k的序号，当k大于R中全部元素时插入点为n。

例如R=[1，2，2，4]，n=4，元素序号为0～3，-1的插入点是0，2的插入点是1，3的插入点是3，4的插入点是3，5的插入点是4。44/61intinsertpoint(vector<int>&R,intk){ intn=R.size(); intlow=0,high=n; while(low<high) //查找区间至少含两个元素 { intmid=(low+high)/2; if(k<=R[mid]) //k<=R[mid]

high=mid;

//在左区间中查找(含R[mid]) else low=mid+1; //在右区间中查找 } returnlow; //返回low}解①由while(low<=high)改为while(low<high)

②由high=mid-1改为high=mid?45/614.3.3查找两个等长有序序列的中位数

对于一个长度为n的有序序列（假设均为递增序列）a[0..n-1]，处于中间位置的元素称为a的中位数（当n为奇数时中位数是唯一的，当n为偶数时有两个中位数，这里指前一个中位数）。

例如，若序列a=（11，13，15，17，19），其中位数是15。若b=（2，4，6，8，20），其中位数为6。

两个等长有序序列的中位数是含它们所有元素的有序序列的中位数，例如a、b两个有序序列的中位数为11。设计一个算法求给定的两个有序序列的中位数。46/61采用二分法求含有n个有序元素的序列a、b的中位数855（1）若n=1，较小者为中位数。解47/61（2）n>1分为3种情况。分别求出a、b的中位数a[m1]和b[m2]：①若a[m1]=b[m2]，则a[m1]或b[m2]即为所求中位数，算法结束。1，3，5，6，92，3，5，8，10548/61②若a[m1]<b[m2]，则舍弃序列a中前半部分（较小的一半），同时舍弃序列b中后半部分（较大的一半）要求舍弃的长度相等。1，3，4，6，92，3，5，8，104，6，92，3，54继续求49/61③若a[m1]>b[m2]，则舍弃序列a中后半部分（较大的一半），同时舍弃序列b中前半部分（较小的一半），要求舍弃的长度相等。舍弃一半即

n/2

个元素。1，3，5，6，92，3，4，8，101,3,54，8，104继续求50/61voidprepart(int&s,int&t) //求a[s..t]序列的前半子序列{ intm=(s+t)/2; t=m;}voidpostpart(int&s,int&t) //求a[s..t]序列的后半子序列{ intm=(s+t)/2; if((s+t)%2==0) //序列中有奇数个元素 s=m; else //序列中有偶数个元素 s=m+1;}[s,t][s,t]（修改：保留的区间）51/61intmidnum11(inta[],ints1,intt1,intb[],ints2,intt2) //被midnum调用{ intm1,m2; if(s1==t1&&s2==t2) //满足情况(1) returna[s1]<b[s2]?a[s1]:b[s2]; else //满足情况(2) { m1=(s1+t1)/2; //求a的中位数 m2=(s2+t2)/2; //求b的中位数 if(a[m1]==b[m2]) //满足① returna[m1]; if(a[m1]<b[m2]) //满足② { postpart(s1,t1); //a取后半部分

prepart(s2,t2); //b取前半部分 returnmidnum11(a,s1,t1,b,s2,t2); } else //满足③ { prepart(s1,t1); //a取前半部分

postpart(s2,t2); //b取后半部分 returnmidnum11(a,s1,t1,b,s2,t2); } }}52/61intmidnum1(inta[],intb[],intn) //递归算法：求有序序列a和b的中位数{returnmidnum11(a,0,n-1,b,0,n-1);}T(n)=1 当n=1T(n)=T(n/2)+1 当n>1容易推出，T(n)=O(log2n)。53/614.3.4查找假币

共有n（n>3）个硬币，编号为0～n-1，其中有且仅有一个假币，假币与真币的外观相同但重量不同，事先知道假币的重量比真币轻还是重。

现在用一架天平称重，天平称重的硬币数没有限制。设计一个算法找出这个假币，使得称重的次数最少。54/6120A2112232425262728BC202112A1B1C112解n=9，9个硬币编号为0～8，假设硬币重2，其中coins[2]=1，light=1（编号2的硬币为较轻的假币）。0～80～23～56～80～01～12～255/61intno; //找到的假币编号intlight; //假币比真币轻（1）或者重（-1）intBalance(vector<int>&c,intia,intib,intn) //c[ia]和c[ib]开始的n个硬币称重一次{ intsa=0,sb=0; for(inti=ia,j=0;j<n;i++,j++) sa+=c[i]; for(inti=ib,j=0;j<n;i++,j++) sb+=c[i]; if(sa<sb)return1; //A轻 elseif(sa==sb)return0; //A，B重量相同 elsereturn-1; //B轻}56/61voidspcoin(vector<int>&coins,inti,intn) //在coins[i..i+n-1]中查找假币{ if(n==1) //剩余1个硬币coins[i] no=i; elseif(n==2) //剩余2个硬币coins[i]和coins[i+1] { intb=Balance(coins,i,i+1,1); //2个硬币称重 if(b==light) //coins[i]是假币 no=i; else //coins[i+1]是假币 no=i+1; } else //剩余3个或者以上硬币 { intk=n/3; intia=i,ib=i+k,ic=i+2*k; //分为A,B,C,硬币个数分别为,k,n-2k intb=Balance(coins,ia,ib,k); //A,B称重一次 if(b==0) //A,B的重量相同，假币在C中 spcoin(coins,ic,n-2*k); //在C中查找假币 elseif(b==light) //假币A中 spcoin(coins,ia,k); //在A中查找假币 elsespcoin(coins,ib,k); //假币在B中，在B中查找假币 }}57/613.3.5*实战—有序数组中的单一元素（LeetCode540）

给定一个只包含整数的有序数组，每个元素都会出现两次，唯有一个数只会出现一次，找出这个数。

例如，nums=[1，1，2，3，3，4，4，8，8]，输出为2。要求设计如下函数，采用算法应该在O(log2n)时间复杂度和O(1)空间复杂度中运行。

要求设计如下函数：class

Solution

{public:

int

singleNonDuplicate(vector<int>&

nums) {

}};58/6110112223344546a[0]=a[1]出现两次a[2]=a[3]出现两次5758a[4]≠a[5]a[6]≠a[7]末尾元素解保证mid为偶数查找第一个a[mid]≠a[mid+1]的mid59/6110112223344546mid=(0+6)/2=3，mid为奇数，置mid=3-1=2，保证mid为偶数10112223344546mida[mid]=a[mid+1]，说明a[0..mid+1]均出现两次，新区间修改为a[mid+2..n-1]的元素344546mid=(4+6)/2=5，mid为奇数，置mid=5-1=4344546a[mid]≠a[mid+1]，查找第一个这样的位置，新区间修改为a[low..mid]元素34区间中只有一个元素，即为所求结果为360/61class

Solution

{public: int

singleNonDuplicate(vector<int>&

nums)

{ int

n=nums.size();

int

low=0,high=n-1;

while(low<high)

//查找区间至少有2个元素时循环

{ int

mid=(low+high)/2;

if(mid%2==1)

//保证mid为偶数

mid--;

if(nums[mid]!=nums[mid+1])

//nums[mid]与右边不同，向左边逼近

high=mid;

else

//nums[mid]=nums[mid+1]

low=mid+2;

//跳过相同的两个元素，在右区间中查找

}

return

nums[low];

//查找区间只有一个元素时即为所求

}};61/6162/61思政案例第4章分治法4.1分治法概述4.2求解排列问题CONTENTS提纲4.3求解查找问题4.5求xn和An问题4.4求解组合问题63/524.4.1最大连续子序列和4.4求解组合问题给定一个含n（n≥1）个整数的序列，要求求出其中最大连续子序列的和。序列（-2，11，-4，13，-5，-2）的最大子序列和为20。序列（-6，2，4，-7，5，3，2，-1，6，-9，10，-2）的最大子序列和为16。规定一个序列最大连续子序列和至少是0，如果小于0，其结果为0。64/52alow

…

amid

amid+1…

ahighmaxLeftBorderSummaxRightBorderSum+max3(maxLeftSum,maxRightSum,maxLeftBorderSum+maxRightBorderSum)alow

…

ai

…

amidamid+1

…

aj

…

ahighmaxLeftSummaxRightSum（a）递归求出maxLeftSum和maxRightSum（b）求出maxLeftBorderSum+maxRightBorderSum（c）求出a序列中最大连续子序列的和解65/52maxLeftBorderSum=7-20111-42133-54-25midmaxLeftSum=11maxRightSum=13（a）递归求出maxLeftSum和maxRightSum-201112133-54-25-4-475maxRightBorderSum=131386（b）以-4为中心的最大连续子序列和为20（c）结果=max3(11，13，20)=2066/52intmax3(inta,intb,intc) //求出3个int整数中的最大值{ returnmax(max(a,b),c);}intmaxSubSum3(vector<int>&a) //递归算法：求a序列中最大连续子序列和{ intn=a.size(); returnmaxSubSum31(a,0,n-1);}67/52intmaxSubSum31(vector<int>&a,intlow,inthigh) //被maxSubSum3调用{ if(low==high) //子序列只有一个元素时 { if(a[low]>0) //该元素大于0时返回它 returna[low]; else //该元素小于或等于0时返回0 return0; }68/52 intmid=(low+high)/2; //求中间位置 intmaxLeftSum=maxSubSum31(a,low,mid); //求左子序列之和 intmaxRightSum=maxSubSum31(a,mid+1,high); //求右子序列之和 intmaxLeftBorderSum=0,lowBorderSum=0; for(inti=mid;i>=low;i--) //求a[i..mid] { lowBorderSum+=a[i]; if(lowBorderSum>maxLeftBorderSum) maxLeftBorderSum=lowBorderSum; } intmaxRightBorderSum=0,highBorderSum=0; for(intj=mid+1;j<=high;j++) //求a[mid+1..j] { highBorderSum+=a[j]; if(highBorderSum>maxRightBorderSum) maxRightBorderSum=highBorderSum; } intans=max3(maxLeftSum,maxRightSum, maxLeftBorderSum+maxRightBorderSum); returnmax(ans,0);}69/52T(n)=1 当n=1T(n)=2T(n/2)+n

当n>1T(n)=O(nlog2n)70/52

有一个2k×2k（k>0）的棋盘，恰好有一个方格与其他方格不同，称之为特殊方格。现在要用如下的L型骨牌覆盖除了特殊方格外的其他全部方格，骨牌可以任意旋转，并且任何两个骨牌不能重叠。请给出一种覆盖方法。4.4.2棋盘覆盖问题71/52

棋盘中的方格数=2k×2k=4k，覆盖使用的L型骨牌个数=(4k-1)/3。

采用的方法是：将棋盘划分为4个大小相同4个象限，根据特殊方格的位置（dr，dc），在中间位置放置一个合适的L型骨牌。

例如，如下图所示，特殊方格在左上角象限中，在中间放置一个覆盖其他3个象限中各一个方格的L型骨牌。特殊方格在左上角象限（dr，dc）放置一个L型骨牌中间位置解72/52k=3，n=23=8333444888999222777555666101010111111111131313141414181818191919121212171717151515161616202020212121左上角象限右上角象限右下角象限左下角象限73/52

用（tr，tc）表示一个象限左上角方格的坐标，（dr，dc）是特殊方格所在的坐标，size是棋盘的行数和列数。

用二维数组board存放覆盖方案，用tile全局变量表示L型骨牌的编号（从整数1开始），board中3个相同的整数表示一个L型骨牌。(tr,tc)(dr,dc)ss左上角（行,列）

74/52intboard[MAX][MAX]; //表示棋盘，MAX为常量inttile=1; //L型骨牌的编号,从1开始voidChessBoard1(inttr,inttc,intdr,intdc,intk) //被ChessBoard调用{ if(k==0)return; //递归出口 intt=tile++; //取一个L型骨，其牌号为tile intsize=1<<(k-1); //分割的子棋盘大小75/52s(tr,tc)(dr,dc)s(tr,tc)(tr+s-1,tc+s-1)ssif(dr<tr+size&&dc<tc+size) //特殊方格在左上角象限中

ChessBoard1(tr,tc,dr,dc,k-1); //继续分割左上角象限else //特殊方格不在左上角象限中{ board[tr+size-1][tc+size-1]=t; //用t号L型骨牌覆盖右下角

ChessBoard1(tr,tc,tr+size-1,tc+size-1,k-1); //继续分割左上角象限}76/52 if(dr<tr+size&&dc>=tc+size)

ChessBoard1(tr,tc+size,dr,dc,size); //特殊方格在右上角象限中 else //特殊方格不在右上角象限中 { board[tr+size-1][tc+size]=t; //用t号L型骨牌覆盖左下角

ChessBoard1(tr,tc+size,tr+size-1,tc+size,k-1); //继续分割右上角象限 } if(dr>=tr+size&&dc<tc+size) //特殊方格在左下角象限中

ChessBoard1(tr+size,tc,dr,dc,k-1); //继续分割左下角象限 else //特殊方格不在左下角象限中 { board[tr+size][tc+size-1]=t; //用t号L型骨牌覆盖右上角

ChessBoard1(tr+size,tc,tr+size,tc+size-1,k-1); //继续分割左下角象限 } if(dr>=tr+size&&dc>=tc+size) //特殊方格在右下角象限中

ChessBoard1(tr+size,tc+size,dr,dc,k-1); //继续分割右下角象限 else //特殊方格在右下角象限中 { board[tr+size][tc+size]=t; //用t号L型骨牌覆盖左上角

ChessBoard1(tr+size,tc+size,tr+size,tc+size,k-1); //继续分割右下角象限 }}77/52voidChessBoard(intdr,intdc,intk) //递归算法，求2^k*2^k棋盘的覆盖问题{

ChessBoard1(0,0,dr,dc,k);}T(k)=1 当k=1T(k)=4T(k-1)+1 当k>1T(n)=O(4k)78/52

设有n=2k个选手要进行网球循环赛，要求设计一个满足以下要求的比赛日程表：

（1）每个选手必须与其他n-1个选手各赛一次。

（2）每个选手一天只能赛一次。

（3）循环赛在n-1天之内结束。4.4.3循环日程安排问题79/522211k=1k=222114433左上角左下角右上角右下角44332211人为添加的表示选手1与选手2比赛加2k-1=2由k=1创建k=2的过程解80/52k=2左上角左下角右上角右下角2211443344332211由k=2创建k=3的过程22114433443322116655887788776655k=3加2k-1=42211443344332211665588778877665581/52

将n=2k问题划分为4部分：

（1）左上角：左上角为2k-1个选手在前半程的比赛日程（k=1时直接给出，否则，上一轮求出的就是2k-1个选手的比赛日程）。

（2）左下角：左下角为另2k-1个选手在前半程的比赛日程，由左上角加2k-1得到，例如22个选手比赛，左下角由左上角直接加2（2k-1）得到，23个选手比赛，左下角由左上角直接加4（2k-1）得到。

（3）右上角：将左下角直接复制到右上角得到另2k-1个选手在后半程的比赛日程。

（4）右下角：将左上角直接复制到右下角得到2k-1个选手在后半程的比赛日程。82/52intk;inta[MAX][MAX]; //存放比赛日程表（行列下标为0的元素不用）voidPlan11(intk) //被Plan1调用{ if(k==1) //求解2个选手比赛日程 { a[1][1]=1;a[1][2]=2; a[2][1]=2;a[2][2]=1; }83/52else{Plan11(k-1); //递归求出2^(k-1)个选手比赛日程安排intn=1<<(k-1);for(inti=n+1;i<=2*n;i++) //填左下角元素for(intj=1;j<=n;j++) a[i][j]=a[i-n][j]+n; //左下角元素和左上角元素的对应关系for(inti=1;i<=n;i++) //填右上角元素for(intj=n+1;j<=2*n;j++)a[i][j]=a[i+n][(j+n)%(2*n)];for(inti=n+1;i<=2*n;i++) //填右下角元素for(intj=n+1;j<=2*n;j++)a[i][j]=a[i-n][j-n];}}84/52voidPlan1(intk) //递归算法：求解循环日程安排问题{

Plan11(k);}T(k)=1 当k=1T(k)=T(k-1)+3×4k-1 当k>1T(n)=O(4k)85/524.4.4求最近点对距离给定若干个二维空间中的点，点的类型Point如下：structPoint //点的类型{ intx,y; Point(intx1,inty1):x(x1),y(y1){} //构造函数};点集采用vector<Point>容器p存放，任意两个不同点之间有一个直线距离，求最近的两个点的距离。86/6对p中所有点按x坐标递增排序，采用分治法策略求解。解S1S2p[mid].xd3垂直带形区ddPLPRXYdld2d=min(d1,d2)87/6d=min(d,d3)ddPLlPRdp1[i]p1中的点按y递增排序。p1中每个点p1[i]在y方向d距离内最多7个点与它的距离小于d。88/6#defineINF0x3f3f3f3f //表示∞intcmpx(Pointa,Pointb) //用于按x递增排序{