算法在信息学奥赛中的应用(分治法)分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。分治法解题的一般步骤：（1）分解，将要解决的问题划分成若干规模较小的同类问题；（2）求解，当子问题划分得足够小时，用较简单的方法解决；（3）合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。分治法应用例1、比赛安排(noip1996)设有2^n(n<=6)个球队进行单循环比赛,计划在2^n-1天内完成,每个队每天进行一场比赛。设计一个比赛的安排,使在2^n-1天内每个队都与不同的对手比赛。例如n=2时的比赛安排为:队1234比赛1-23-4第一天1-32-4第二天1-42-3第三天算法分析：此题很难直接给出结果，我们先将问题进行分解，设m=2^n，将规模减半，如果n=3(即m=8),8个球队的比赛，减半后变成4个球队的比赛（m=4），4个球队的比赛的安排方式还不是很明显，再减半到两个球队的比赛(m=2)，两个球队的比赛安排方式很简单，只要让两个球队直接进行一场比赛即可：1221分析两个球队的比赛的情况不难发现，这是一个对称的方阵，我们把这个方阵分成4部分（即左上，右上，左下，右下），右上部分可由左上部分加1（即加m/2）得到，而右上与左下部分、左上与右下部分别相等。因此我们也可以把这个方阵看作是由M=1的方阵所成生的，同理可得M=4的方阵：1234214334124321同理可由M=4方阵生成M=8的方阵：1234567821436587341278564321876556781234658721437856341287654321这样就构成了整个比赛的安排表。在算法设计中，用数组a记录2^n个球队的循环比赛表，整个循环比赛表从最初的1*1方阵按上述规则生成2*2的方阵，再生成4*4的方阵，……直到生成出整个循环比赛表为止。变量h表示当前方阵的大小,也就是要生成的下一个方阵的一半。源程序：vari,j,h,m,n:integer;a:array[1..32,1..32]ofinteger;beginreadln(n);m:=1;a[1,1]:=1;h:=1;fori:=1tondom:=m*2;repeatfori:=1tohdoforj:=1tohdobegina[i,j+h]:=a[i,j]+h;{构造右上角方阵}a[i+h,j]:=a[i,j+h];{构造左下角方阵}a[i+h,j+h]:=a[i,j];{构造右下角方阵}end;h:=h*2;untilh=m;fori:=1tomdobeginforj:=1tomdowrite(a[i,j]:4);writeln;end;end.在分治算法中，若将原问题分解成两个较小的子问题，我们称之为二分法，由于二分法划分简单，所以使用非常广泛。使用二分法与使用枚举法求解问题相比较，时间复杂度由O（N）降到O（log2N），在很多实际问题中，我们可以通过使用二分法，达到提高算法效率的目的，如下面的例子。例2一元三次方程求解（noip2001tg）题目大意：给出一个一元三次方程f(x)=ax3+bx2+cx+d=0,求它的三个根。所有的根都在区间[-100，100]中，并保证方程有三个实根，且它们之间的差不小于1。算法分析：在讲解枚举法时，我们讨论了如何用枚举法求解此题，但如果求解的精度进一步提高，使用枚举法就无能为力了，在此我们再一次讨论如何用二分法求解此题。由题意知（i,i+1）中若有根，则只有一个根，我们枚举根的值域中的每一个整数x(-100≤x≤100),设定搜索区间[x1，x2]，其中x1=x，x2=x+1。若：⑴f(x1)=0，则确定x1为f(x)的根；⑵f(x1)*f(x2)<0，则确定根x在区间[x1，x2]内。⑶f(x1)*f(x2)>0，则确定根x不在区间[x1，x2]内，设定[x2，x2+1]为下一个搜索区间；若确定根x在区间[x1，x2]内，采用二分法，将区间[x1，x2]分成左右两个子区间：左子区间[x1，x]和右子区间[x，x2]（其中x=（x1+x2）/2）。如果f(x1)*f(x)≤0，则确定根在左区间[x1，x]内，将x设为该区间的右界值（x2=x），继续对左区间进行对分；否则确定根在右区间[x，x2]内，将x设为该区间的左界值（x1=x），继续对右区间进行对分；上述对分过程一直进行到区间的间距满足精度要求为止（即x2-x1<0.005）。此时确定x1为f(x)的根。源程序：{$N+}varx:integer;a,b,c,d,x1,x2,xx:extended;functionf(x:extended):extended;beginf:=((a*x+b)*x+c)*x+d;end;beginread(a,b,c,d);forx:=-100to100dobeginx1:=x;x2:=x+1;iff(x1)=0thenwrite(x1:0:2,'')elseiff(x1)*f(x2)<0thenbeginwhilex2-x1>=0.005dobeginxx:=(x1+x2)/2;iff(x1)*f(xx)<=0thenx2:=xxelsex1:=xx;end;{while}write(x1:0:2,'');end;{then}end;{for}end.
