2019-2020年高中信息技术 全国青少年奥林匹克联赛教案 分治法.doc

2019-2020年高中信息技术 全国青少年奥林匹克联赛教案 分治法分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。分治法解题的一般步骤：（1）分解，将要解决的问题划分成若干规模较小的同类问题；（2）求解，当子问题划分得足够小时，用较简单的方法解决；（3）合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。分治法应用例1、 比赛安排(noip1996)设有2n(n=6)个球队进行单循环比赛,计划在2n-1天内完成,每个队每天进行一场比赛。设计一个比赛的安排,使在2n-1天内每个队都与不同的对手比赛。例如n=2时的比赛安排为:队 1 2 3 4比赛 1-2 3-4 第一天1-3 2-4 第二天1-4 2-3 第三天算法分析：此题很难直接给出结果，我们先将问题进行分解，设m=2n，将规模减半，如果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记录2n个球队的循环比赛表，整个循环比赛表从最初的1*1方阵按上述规则生成2*2的方阵，再生成4*4的方阵，直到生成出整个循环比赛表为止。变量h表示当前方阵的大小,也就是要生成的下一个方阵的一半。源程序：var i,j,h,m,n:integer; a:array1.32,1.32of integer;begin readln(n); m:=1;a1,1:=1;h:=1;for i:=1 to n do m:=m*2; repeat for i:=1 to h do for j:=1 to h do begin ai,j+h:=ai,j+h;构造右上角方阵 ai+h,j:=ai,j+h;构造左下角方阵 ai+h,j+h:=ai,j;构造右下角方阵 end; h:=h*2; until h=m; for i:=1 to m do begin for j:=1 to m do write(ai,j:4); writeln; end;end.在分治算法中，若将原问题分解成两个较小的子问题，我们称之为二分法，由于二分法划分简单，所以使用非常广泛。使用二分法与使用枚举法求解问题相比较，时间复杂度由O（N）降到O（log2N），在很多实际问题中，我们可以通过使用二分法，达到提高算法效率的目的，如下面的例子。例2 一元三次方程求解（noipxxtg） 题目大意：给出一个一元三次方程f(x)=ax3+bx2+cx+d=0 ,求它的三个根。所有的根都在区间-100，100中，并保证方程有三个实根，且它们之间的差不小于1。算法分析：在讲解枚举法时，我们讨论了如何用枚举法求解此题，但如果求解的精度进一步提高，使用枚举法就无能为力了，在此我们再一次讨论如何用二分法求解此题。由题意知（i,i+1）中若有根，则只有一个根，我们枚举根的值域中的每一个整数x(-100x100),设定搜索区间x1，x2，其中x1=x，x2=x+1。若：f(x1)=0，则确定x1为f(x)的根；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-x10.005）。此时确定x1为f(x)的根。源程序：$N+var x:integer; a,b,c,d,x1,x2,xx:extended;function f(x:extended):extended;begin f:=(a*x+b)*x+c)*x+d;end;begin read(a,b,c,d); for x:=-100 to 100 do begin x1:=x;x2:=x+1; if f(x1)=0 then write(x1:0:2, ) else if f(x1)*f(x2)=0.005 do begin xx:=(x1+x2)/2; if f(x1)*f(xx)=0 then x2:=xx else x1:=xx; end;while write(x1:0:2, ); end; then end;forend.