第7章--分治算法(C++版)

第七章分治算法所谓分治就是指的分而治之，即将较大规模的问题分解成几个较小规模的问题，通过对较小规模问题的求解达到对整个问题的求解。当我们将问题分解成两个较小问题求解时的分治方法称之为二分法。你们玩过猜数字的游戏吗？你的朋友心里想一个1000以内的正整数，你可以给出一个数字x，你朋友只要回答“比x大”或者“比x小”或者“猜中”，你能保证在10次以内猜中吗？运气好只要一次就猜中。开始猜测是1到1000之间，你可以先猜500，运气好可以一次猜中，如果答案比500大，显然答案不可能在1到500之间，下一次猜测的区间变为501到1000，如果答案比500小，那答案不可能在500到1000之间，下一次猜测的区间变为1到499。只要每次都猜测区间的中间点，这样就可以把猜测区间缩小一半。由于，因此不超过10次询问区间就可以缩小为1，答案就会猜中了，这就是二分的基本思想。每一次使得可选的范围缩小一半，最终使得范围缩小为一个数，从而得出答案。假设问的范围是1到n，根据,所以我们只需要问O(logn)次就能知道答案了。需要注意的是使用二分法有一个重要的前提，就是有序性，下面通过几个例子来体会二分法的应用。12100010nxxn2log12得例7.1找数描述：给一个长度为n的单调递增的正整数序列，即序列中每一个数都比前一个数大。有m个询问，每次询问一个x，问序列中最后一个小于等于x的数是什么？输入：第一行两个整数n,m。接下来一行n个数，表示这个序列。接下来m行每行一个数，表示一个询问。输出：输出共m行，表示序列中最后一个小于等于x的数是什么。假如没有输出-1。样例输入：5312346513样例输出：413分析：我们用Left表示询问区间的左边界，用Right表示询问区间的右边界，[Left,Right]组成询问区间。一开始Left=1，Right=n，我们可以把原始序列的左边想象成若干个无穷小的数，把序列的右边想象成无穷大的数，这样比较好理解。序列已经按照升序排好，保证了二分的有序性。每一次二分，我们这样来做：①取区间中间值Mid=(Left+Right)/2；②判断Mid与x的关系，如果a[Mid]x，由于序列是升序排列，所以区间[Mid,Right]都可以被排除，修改右边界Right=Mid-1；③如果a[Mid]=x，修改左边界Left=Mid+1；重复执行二分操作直到LeftRight。下面我们来分析答案的情况。循环结束示意图如下：LeftRight大于x小于等于x最终循环结束时一定是Left=Right+1，根据二分第②步的做法我们知道Right的右边一定都是大于x的，而根据第③步我们可以知道Left左边一定是小于等于x的。所以，一目了然，最终答案是Right指向的数。Right=0就是题目中输出-1的情况。程序如下：#includeiostreamusingnamespacestd;intn,m,a[110000];intmain(){cinnm;for(inti=1;i=n;i++)cina[i];a[0]=-1;for(inti=1;i=m;i++){intx;intleft=1,right=n,mid;cinx;while(left=right){mid=(left+right)/2;if(a[mid]=x)left=mid+1;elseright=mid-1;}couta[right]endl;}return0;}例7.2快速排序(Quicksort)快速排序由C.A.R.Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。设要排序的数组是A[0]……A[N-1]，首先任意选取一个数据（通常选用数组的中间数）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。值得注意的是，快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。一趟快速排序的算法是：1．设置两个变量i、j，排序开始的时候：i=0，j=N-1；2．以数组中任意元素作为关键数据(一般以数组中间元素作为关键数据)，赋值给key，可以是key=A[(i+j)/2]；3.从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于等于key的值A[j]；4．从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于等于key的A[i]；5.交换A[i]和A[j]的值，同时i++,j--；6．重复第3、4、5步，直到ij；例如有8个元素需要排序：6101184197一趟快速排序后：此时ij,并且i左边的数字都小于等于key,j右边的数字都大于等于key，进而接下来可以分别对左边段[0,j]和右边段[i,N-1]利用同样的方法排序。【程序实现】voidqsort(intle,intri){inti=le,j=ri,mid=a[(le+ri)/2];while(i=j)//注意这里要有等号{while(a[i]mid)i++;//在左边找大于等于mid的数while(a[j]mid)j--;//在右边找小于等于mid的数if(i=j){swap(a[i],a[j]);//交换i++,j--;//继续找}}if(lej)qsort(le,j);//分别递归继续排序if(iri)qsort(i,ri);}快速排序(Quicksort)是对冒泡排序的一种改进，快速排序的时间复杂度是O(nlogn)，速度快，但它是不稳定的排序方法。就平均时间而言，快速排序是目前被认为是最好的一种内部排序的方法。但快速排序需要一个栈空间来实现递归，若每一趟排序都将记录序列均匀地分割成长度相近的两个子序列，则栈的最大深度为log(n+1)。【例3】一元三次方程求解有形如：ax3+bx2+cx+d＝0这样的一个一元三次方程。给出该方程中各项的系数（a,b,c,d均为实数），并约定该方程存在三个不同实根（根的范围在-100至100之间），且根与根之差的绝对值≥1。要求由小到大依次在同一行输出这三个实根（根与根之间留有空格），并精确到小数点后2位。提示：记方程f（x）=0，若存在2个数x1和x2，且x1x2，f（x1）*f（x2）＜0，则在（x1，x2）之间一定有一个根。输入：a，b，c，d输出：三个实根（根与根之间留有空格）【输入输出样例】输入：1-5-420输出：-2.002.005.00【算法分析】这是一道有趣的解方程题。为了便于求解，设方程f(x)=ax3+bx2+cx+d＝0，设根的值域（-100至100之间）中有x，其左右两边相距0.0005的地方有x1和x2两个数，即x1=x-0.0005，x2=x+0.0005。x1和x2间的距离（0.001）满足精度要求（精确到小数点后2位）。若出现如图1所示的两种情况之一，则确定x为f(x)=0的根。有两种方法计算f(x)=0的根x:1．枚举法根据根的值域和根与根之间的间距要求(≥1)，我们不妨将根的值域扩大100倍(-10000≤x≤10000)，依次枚举该区间的每一个整数值x，并在题目要求的精度内设定区间：x1=，x2=。若区间端点的函数值f(x1)和f(x2)异号或者在区间端点x1的函数值f(x1)=0，则确定为f(x)=0的一个根。由此得出算法：输入方程中各项的系数a，b，c，d；for(x=-10000;x=10000;x++)//枚举当前根*100的可能范围{x1=(x-0.05)/100；x2=(x+0.05)/100；//在题目要求的精度内设定区间if(f(x1)*f(x2)0||f(x1)==0)//若在区间两端的函数值异号或在x1处的函数值为0，则确定x/100为根printf(“%.2f”,x/100)；}其中函数f(x)计算x3+b*x2+c*x+d：doublef(doublex)//计算x3+b*x2+c*x+d{f=x*x*x+b*x*x+c*x+d；}//f函数2.分治法枚举根的值域中的每一个整数x(-100≤x≤100)。由于根与根之差的绝对值≥1，因此设定搜索区间[x1，x2]，其中x1=x，x2=x+1。若⑴f(x1)=0，则确定x1为f(x)的根；⑵f(x1)*f(x2)0，则确定根x不在区间[x1，x2]内，设定[x2，x2+1]为下一个搜索区间⑶f(x1)*f(x2)0，则确定根x在区间[x1，x2]内。如果确定根x在区间[x1，x2]内的话（f(x1)*f(x2)0），如何在该区间找到根的确切位置。采用二分法，将区间[x1，x2]分成左右两个子区间：左子区间[x1，x]和右子区间[x，x2]（其中x=）：如果f(x1)*f(x)≤0，则确定根在左区间[x1，x]内，将x设为该区间的右指针（x2=x），继续对左区间进行对分；如果f(x1)*f(x)0，则确定根在右区间[x，x2]内，将x设为该区间的左指针（x1=x），继续对右区间进行对分；上述对分过程一直进行到区间的间距满足精度要求为止（x2-x10.001）。此时确定x1为f(x)的根。由此得出算法：输入方程中各项的系数a，b，c，d；{for(x=-100;x=100;x++)//枚举每一个可能的根{x1=x;x2=x+1;//确定根的可能区间if(f(x1)==0)printf(%.2f,x1);//若x1为根，则输出elseif(f(x1)*f(x2)0)//若根在区间[x1，x2]中{while(x2-x1=0.001)//若区间[x1，x2]不满足精度要求，则循环{xx=(x2+x1)/2;//计算区间[x1，x2]的中间位置if((f(x1)*f(xx))=0)//若根在左区间，则调整右指针x2=xx;elsex1=xx;//若根在右区间，则调整左指针}printf(%.2f,x1);//区间[x1，x2]满足精度要求，确定x1为根}}coutendl;}doublef(doublex)//将x代入函数{return(x*x*x*a+b*x*x+x*c+d);}其中f(x)的函数说明如枚举法所示。【例4】、循环比赛日程表（match）【问题描述】设有N个选手进行循环比赛，其中N=2M，要求每名选手要与其他N-1名选手都赛一次，每名选手每天比赛一次，循环赛共进行N-1天，要求每天没有选手轮空。输入：M输出：表格形式的比赛安排表【样例输入】match.in3【样例输出】match.out1234567821436587341278564321876556781234658721437856341287654321【问题分析】以M=3(即N=23=8)为例，可以根据问题要求，制定出如下图所示的一种方案：以表格的中心为拆分点，将表格分成A、B、C、D四个部分，就很容易看出有A=D，B=C，并且，这一规律同样适用于各个更小的部分。设有n个选手的循环比赛，其中n=2m，要求每名选手要与其他n-1名选手都赛一次。每名选手每天比赛一次，循环赛共进行n-1天。要求每天没有选手轮空.以下是八名选手时的循环比赛表，表中第一行为八位选手的编号，下面七行依次是每位选手每天的对手。1234567821436587341278564321876556781234658721437856341287654321【算法分析】从八位选手的循环比赛表中可以看出,这是一个具有对称性的方阵,可以把方阵一分为四来看,那么左上角的4*4的方阵就是前四位选手的循环比赛表,而右上角的4*4的方阵就是后四位选手的循环比赛表,它们在本质上是一样的,都是4个选手的循环比赛表,所不同的只是选手编号不同而已,将左上角中方阵的所有元素加上4就能得到右上角的方阵.下方的