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

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第七章 分治算法,所谓分治就是指的分而治之，即将较大规模的问题分解成几个较小规模的问题，通过对较小规模问题的求解达到对整个问题的求解。当我们将问题分解成两个较小问题求解时的分治方法称之为二分法。,你们玩过猜数字的游戏吗？你的朋友心里想一个,1000,以内的正整数，你可以给出一个数字,x,，你朋友只要回答,“,比,x,大,”,或者,“,比,x,小,”,或者,“,猜中,”,，你能保证在,10,次以内猜中吗？运气好只要一次就猜中。,开始猜测是,1,到,1000,之间，你可以先猜,500,，运气好可以一次猜中，如果答案比,500,大，显然答案不可能在,1,到,500,之间，下一次猜测的区间变为,501,到,1000,，如果答案比,500,小，那答案不可能在,500,到,1000,之间，下一次猜测的区间变为,1,到,499,。只要每次都猜测区间的中间点，这样就可以把猜测区间缩小一半。由于 ，因此不超过,10,次询问区间就可以缩小为,1,，答案就会猜中了，这就是二分的基本思想。,每一次使得可选的范围缩小一半，最终使得范围缩小为一个数，从而得出答案。假设问的范围是,1,到,n,，根据,所以我们只需要问,O(logn,),次就能知道答案了。,需要注意的是使用二分法有一个重要的前提，就是有序性，下面通过几个例子来体会二分法的应用。,例,7.1,找数,描述：,给一个长度为,n,的单调递增的正整数序列，即序列中每一个数都比前一个数大。有,m,个询问，每次询问一个,x,，问序列中最后一个小于等于,x,的数是什么？,输入：,第一行两个整数,n,m,。,接下来一行,n,个数，表示这个序列。,接下来,m,行每行一个数，表示一个询问。,输出：,输出共,m,行，表示序列中最后一个小于等于,x,的数是什么。假如没有输出,-1,。,样例输入：,5 3,1 2 3 4 6,5,1,3,样例输出：,4,1,3,分析：,我们用,Left,表示询问区间的左边界，用,Right,表示询问区间的右边界，,Left,Right,组成询问区间。一开始,Left=1,，,Right=n,，我们可以把原始序列的左边想象成若干个无穷小的数，把序列的右边想象成无穷大的数，这样比较好理解。序列已经按照升序排好，保证了二分的有序性。每一次二分，我们这样来做：取区间中间值,Mid=(Left+Right)/2,；判断,Mid,与,x,的关系，如果,aMid,x,，由于序列是升序排列，所以区间,Mid,Right,都可以被排除，修改右边界,Right=Mid-1,；如果,aMid,Right,。下面我们来分析答案的情况。循环结束示意图如下：,最终循环结束时一定是,Left=Right+1,，根据二分第步的做法我们知道,Right,的右边一定都是大于,x,的，而根据第步我们可以知道,Left,左边一定是小于等于,x,的。所以，一目了然，最终答案是,Right,指向的数。,Right=0,就是题目中输出,-1,的情况。,程序如下：,#include using namespace std;,int,n,m,a110000;,int,main(),cin,n m;for(,int,i=1;i,ai,;a0=-1;for(,int,i=1;i x;while(left=right)mid=(left+right)/2;if(,amid,=x)left=mid+1;else right=mid-1;,cout,aright,j,；例如有,8,个元素需要排序：,6 10 11 8 4 1 9 7,一趟快速排序后：此时,ij,并且,i,左边的数字都小于等于,key,j,右边的数字都大于等于,key,，进而接下来可以分别对左边段,0,j,和右边段,i,N-1,利用同样的方法排序。,【,程序实现,】,void,qsort(int,le,int,ri,),int,i=le,j=,ri,mid=a(le+ri)/2;,while(i,=j)/,注意这里要有等号,while(ai,mid)j-;/,在右边找小于等于,mid,的数,if(i,=j),swap(ai,aj,);/,交换,i+,j-;/,继续找,if(le,j),qsort(le,j,);/,分别递归继续排序,if(i,ri,),qsort(i,ri,);,快速排序,(,Quicksort,),是对冒泡排序的一种改进，快速排序的时间复杂度是,O(nlogn,),，速度快，但它是不稳定的排序方法。就平均时间而言，快速排序是目前被认为是最好的一种内部排序的方法。但快速排序需要一个栈空间来实现递归，若每一趟排序都将记录序列均匀地分割成长度相近的两个子序列，则栈的最大深度为,log(n+1),。,【,例,3】,一元三次方程求解,有形如：,ax,3,+bx,2,+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-4 20,输出：,-2.00 2.00 5.00,【,算法分析,】,这是一道有趣的解方程题。为了便于求解，设方程,f(x,)=ax,3,+bx,2,+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 x10000),，依次枚举该区间的每一个整数值,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,，则确定根,x,不在区间,x1,，,x2,内，设定,x2,，,x2+1,为下一个搜索区间,f(x1)*f(x2)0,，则确定根,x,在区间,x1,，,x2,内。,如果确定根,x,在区间,x1,，,x2,内的话（,f(x1)*f(x2)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,为根，则输出,else if(f(x1)*f(x2)=0.001)/,若区间,x1,，,x2,不满足精度要求，则循环,xx=(x2+x1)/2;/,计算区间,x1,，,x2,的中间位置,if(f(x1)*,f(xx,)=0)/,若根在左区间，则调整右指针,x2=xx;,else x1=xx;/,若根在右区间，则调整左指针,printf(%.2f ,x1);/,区间,x1,，,x2,满足精度要求，确定,x1,为根,cout,endl,;,double,f(double,x)/,将,x,代入函数,return(x*x*x*,a+b,*x*,x+x,*,c+d,);,其中,f(x,),的函数说明如枚举法所示。,【,例,4】,、循环比赛日程表（,match,）,【,问题描述,】,设有,N,个选手进行循环比赛，其中,N=2,M,，要求每名选手要与其他,N-1,名选手都赛一次，每名选手每天比赛一次，循环赛共进行,N-1,天，要求每天没有选手轮空。,输入：,M,输出：表格形式的比赛安排表,【,样例输入,】,match.in,3,【,样例输出,】,match.out,1 2 3 4 5 6 7 8,2 1 4 3 6 5 8 7,3 4 1 2 7 8 5 6,4 3 2 1 8 7 6 5,5 6 7 8 1 2 3 4,6 5 8 7 2 1 4 3,7 8 5 6 3 4 1 2,8 7 6 5 4 3 2 1,【,问题分析,】,以,M=3(,即,N=2,3,=8),为例，可以根据问题要求，制定出如下图所示的一种方案：,以表格的中心为拆分点，将表格分成,A,、,B,、,C,、,D,四个部分，就很容易看出有,A=D,，,B=C,，并且，这一规律同样适用于各个更小的部分。,设有,n,个选手的循环比赛，其中,n=2,m,，要求每名选手要与其他,n-1,名选手都赛一次。每名选手每天比赛一次，循环赛共进行,n-1,天。要求每天没有选手轮空,.,以下是八名选手时的循环比赛表，表中第一行为八位选手的编号，下面七行依次是每位选手每天的对手。,1 2 3 4 5 6 7 8,2 1 4 3 6 5 8 7,3 4 1 2 7 8 5 6,4 3 2 1 8 7 6 5,5 6 7 8 1 2 3 4,6 5 8 7 2 1 4 3,7 8 5 6 3 4 1 2,8 7 6 5 4 3 2 1,【,算法分析,】,从八位选手的循环比赛表中可以看出,这是一个具有对称性的方阵,可以把方阵一分为四来看,那么左上角的,4*4,的方阵就是前四位选手的循环比赛表,而右上角的,4*4,的方阵就是后四位选手的循环比赛表,它们在本质上是一样的,都是,4,个选手的循环比赛表,所不同的只是选手编号不同而已,将左上角中方阵的所有元素加上,4,就能得到右上角的方阵,.,下方的两个方阵表示前四位选手和后四位选手进行交叉循环比赛的情况,同样具有对称性,将右上角方阵复制到左下角即得到,1,2,3,4,四位选手和,5,6,7,8,四位选手的循环比赛表,根据对称性,右下角的方阵应与左上角的方阵相同,.,这样,八名选手的循环比赛表可以由四名选手的循环比赛表根据对称性生成出来,.,同样地,四名选手的循环比赛表可以由二名选手的循环比赛表根据对称性生成出来,而两名选手的循环比赛表可以说是已知的,这种程序设计方法叫做分治法,其基本思想是把一个规模为,n,的问题分成若干个规模较小的问题,使得从这些较小问题的解易于构造出整个问题的解。,程序中用数组,matchlist,记录,n,名选手的循环比赛表,整个循环比赛表从最初的,1*1,的方阵按上述规则生成出,2*2,的方阵,再生成出,4*4,的方阵,，直到生成出整个循环比赛表为止,.,变量,half,表示当前方阵的大小,也是要生成的下一个方阵的大小的一半。,【,参考程序,】,#include,const,int,MAXN=33,MAXM=5;,int,matchlistMAXNMAXN,;,int,m;,int,main(),printf(Input,m:);,scanf(%d,&m,);,int,n=1,m,k,=1,half=1;/1m,相当于,2m,matchlist00=1;,while(k=m),for(,int,i=0;i,half;i,+)/,构造右上方方阵,for(,int,j=0;j,half;j,+),matchlistij+half,=,matchlistij+half,;,for(,int,i=0;i,half;i,+)/,对称交换构造下半部分方阵,for(,int,j=0;j,half;j,+),matchlisti+halfj,=,matchlistij+half,;,/,左下方方阵等于右上方方阵,matchlisti+halfj+half,=,matchlistij,;,/,右下方方阵等于左上方方阵,half*=2;,k+;,for(,int,i=0;i,n;i,+),for(,int,j=0;j,n;j,+),printf(%4d,matchlistij);,putchar(n,);,return 0;,【,例,5】,取余运算（,mod,）,【,问题描述,】,输入,b,，,p,，,k,的值，求,bp,mod k,的值。其中,b,，,p,，,k*k,为长整形数。,【,输入样例,】,mod.in,2 10 9,【,输出样例,】,mod.out,210 mod 9=7,【,算法分析,】,本题主要的难点在于数据规模很大（,b,，,p,都是长整型数），对于,bp,显然不能死算，那样的话时间复杂度和编程复杂度都很大。,下面先介绍一个原理：,A*B%K=(A%K)*(B%K)%K,。显然有了这个原理，就可以把较大的幂分解成较小的，因而免去高精度计算等复杂过程。那么怎样分解最有效呢？,显然对于任何一个自然数,P,，有,P=2*P/2+P%2,，如,19=2*19/2+19%2=2*9+1,，利用上述原理就可以把,B,的,19,次方除以,K,的余数转换为求,B,的,9,次方除以,K,的余数，即,B,19,=B,2*9+1,=B*B,9,*,B,9,，再进一步分解下去就不难求得整个问题的解。,【,参考程序,】,#include,#include,using namespace std;,int,b,p,k,a,;,int,f(int,p)/,利用分治求,bp,%k,if(p=0)return 1;/b0%k=1,int,tmp,=f(p/2)%k;,tmp,=(,tmp,*,tmp,)%k;/,bp,%k=(b(p/2)2%k,if(p%2=1),tmp,=(,tmp,*b)%k;/,如果,p,为奇数，则,bp,%,return,tmp,;/k=(b(p/2)2)*,b%k,int,main(),cin,bpk;/,读入,3,个数,int,tmpb,=b;/,将,b,的值备份,b%=k;/,防止,b,太大,printf(%d%d,mod%d=%,dn,tmpb,p,k,f(p,);/,输出,return 0;,【,例,8】,、黑白棋子的移动（,chessman,）,【,问题描述,】,有,2n,个棋子（,n4,）排成一行，开始位置为白子全部在左边，黑子全部在右边，如下图为,n=5,的情形：,移动棋子的规则是：每次必须同时移动相邻的两个棋子，颜色不限，可以左移也可以右移到空位上去，但不能调换两个棋子的左右位置。每次移动必须跳过若干个棋子（不能平移），要求最后能移成黑白相间的一行棋子。如,n=5,时，成为：,任务：编程打印出移动过程。,【,输入样例,】,chessman.in,7,【,输出样例,】,chessman.out,step 0:ooooooo*-,step 1:oooooo-*o*,step 2:oooooo*-o*,step 3:ooooo-*o*o*,step 4:ooooo*-o*o*,step 5:oooo-*o*o*o*,step 6:oooo*-o*o*o*,step 7:ooo-*o*o*o*o*,step 8:ooo*o*-*o*o*o*,step 9:o-*o*,oo,*o*o*o*,step10:o*o*o*-o*o*o*o*,step11:-o*o*o*o*o*o*o*,【,算法分析,】,我们先从,n=4,开始试试看，初始时：,第,1,步：,表示空位,第,2,步：,第,3,步：,第,4,步：,第,5,步：,如果,n=5,呢？我们继续尝试，希望看出一些规律，初始时：,第,1,步：,第,2,步：,这样，,n=5,的问题又分解成了,n=4,的情况，下面只要再做一下,n=4,的,5,个步骤就行了。同理，,n=6,的情况又可以分解成,n=5,的情况，,，所以，对于一个规模为,n,的问题，我们很容易地就把他分治成了规模为,n-1,的相同类型子问题。,数据结构如下：数组,c1.max,用来作为棋子移动的场所，初始时，,c1cn,存放白子（用字符,o,表示），,cn+1c2n,存放黑子（用字符*表示），,c2n+1,，,c2n+2,为空位置（用字符,表示）。最后结果在,c3c2n+2,中。,【,参考程序,】,#include,using namespace std;,int,n,st,sp,;,char c101;,void print()/,打印,int,i;,cout,step,st,:;,for(i=1;i=2*n+2;i+),cout,ci,;,cout,endl,;,st,+;,void,init(int,n)/,初始化,int,i;,st,=0;,sp=2*n+1;,for(i=1;i=,n;i,+),ci,=o;,for(i=n+1;i=2*,n;i,+),ci,=*;,c2*n+1=-;c2*n+2=-;,print();,void,move(int,k)/,移动一步,int,j;,for(j=0;jn;,init(n);,mv(n,);,【,上机练习,】,1,、方程,f(x,),的根,【,问题描述,】,求方程,f(x,)=2x+3x-4x=0,在,1,，,2,内的根。,提示：,2x,可以表示成,exp(x,*log(2),的形式。,【,输入格式,】,输入：,1,，,2,的区间值。,【,输出格式,】,输出：方程,f(x,)=0,的根，,x,的值精确小数点,10,位。,【,输入样例,】,1 2,【,输出样例,】,1.5071105957,2,、求一元三次方程的解,【,问题描述,】,有形如：,ax,3,+bx,2,+cx+d=0,一元三次方程。给出该方程中各项的系数,(a,，,b,，,c,，,d,均为实数,),，并约定该方程存在三个不同实根,(,根的范围在,-100,至,100,之间,),，且根与根之差的绝对值,=1,。要求由小到大依次在同一行上输出这三个实根。,【,输入格式,】,输入：,a,，,b,，,c,，,d,【,输出格式,】,输出：三个实根（根与根之间留有空格）,【,输入样例,】,Equ.in,1 5 4 20,【,输出样例,】,Equ.out,-2.00 2.00 5.00,3,、求逆序对,给定一个序列,a,1,a,2,a,n,，如果存在,i,aj,，那么我们称之为逆序对，求逆序对的数目。,【,输入格式,】,第一行为,n,表示序列长度，接下来的,n,行，第,i+1,行表示序列中的第,i,个数。,【,输出格式,】,所有逆序对总数。,【,输入样例,】,deseq,.in,4,3,2,3,2,【,输出样例,】,deseq.out,3,【,数据范围,】,N=10,5,，,A,i,=10,5,。,4,、麦森数（,mason,）,【,问题描述,】,形如,2,P,-1,的素数称为麦森数，这时,P,一定也是个素数。但反过来不一定，即如果,P,是个素数，,2,P,-1,不一定也是素数。到,1998,年底，人们已找到了,37,个麦森数。最大的一个是,P=3021377,，它有,909526,位。麦森数有许多重要应用，它与完全数密切相关。,任务：从文件中输入,P,（,1000P3100000,），计算,2,P,-1,的位数和最后,500,位数字（用十进制高精度数表示）。,【,输入格式,】,文件中只包含一个整数,P,（,1000P3100000,）。,【,输出格式,】,第一行：十进制高精度数,2,P,-1,的位数；,第,2-11,行：十进制高精度数,2,P,-1,的最后,500,位数字（每行输出,50,位，共输出,10,行，不足,500,位时高位补,0,）；,不必验证,2,P,-1,与,P,是否为素数。,【,输入样例,】,mason.in,1279,【,输出样例,】,mason.out,386,00000000000000000000000000000000000000000000000000,00000000000000000000000000000000000000000000000000,00000000000000104079321946643990819252403273640855,38615262247266704805319112350403608059673360298012,23944173232418484242161395428100779138356624832346,49081399066056773207629241295093892203457731833496,61583550472959420547689811211693677147548478866962,50138443826029173234888531116082853841658502825560,46662248318909188018470682222031405210266984354887,32958028878050869736186900714720710555703168729087,