论分治算法在信息学竞赛中的应用

1、论分治算法在信息学竞赛中的应用绍兴县鲁迅中学教技处 夏红军一、问题的提出【例1】寻找假币（Noip2006初赛普及组问题求解第二题）【问题描述】现有80枚硬币，其中有一枚是假币，其重量稍轻，所有真币的重量都相同，如果使用不带砝码的天平称重，最少需要称几次，就可以找出假币？你还要指出第1次的称重方法。二、问题的分析1、直接的想法是将这些硬币2枚一组分为40组，每次只称一组硬币，若发现轻的则为假币，最坏情况下称40次才可找出假币。2、仔细思考上面的分法比较一次只能排除2枚硬币，利用只有一枚假币的性质，我们试着改变一下方法：将所有硬币平均分为两组，每次称两组硬币，这样比较一次可排除一半硬币，最坏情况

2、下只需称7次。3、显然每比较一次能排除的硬币越多越好，朝着这个目标对怎样分组进一步思考。三、问题的解决把所有的硬币尽量平均地分成三组，至少有两组硬币数是相同的，每次称相同的两组，这样每比较一次可排除约2/3的硬币数，最坏情况下只需称4次。四、算法的引入通常我们将这种以大化小的设计思想称之为分治算法，即“分而治之”的意思。也就是说，当我们处理大规模问题时，可以将原问题分解成k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，而且在求出了这些子问题的解之后，还可找到适当的方法把它们合并成整个问题的解。分治算法一般分为三个步骤：分解(Divide)：将原问题分成一系列子问题。求解(Conqu

3、er)：若子问题足够小，则可直接求解。合并(combine)；将子问题的结果合并成原问题的解。可以看出，为实现分治算法，一个方法是借助递归结构，另一个方法是从已知的小问题出发进行递推，小问题层层合并成大问题后解决。递归大致过程如下：Divide-and-Conquer(P)1. if |P|n0 2. then return(ADHOC(P)3. 将P分解为较小的子问题 P1 ,P2 ,.,Pk 4. for i1 to k 5. do yi Divide-and-Conquer(Pi) 递归解决Pi6. T MERGE(y1,y2,.,yk) 合并子问题7. return(T)其中|P|表示

4、问题P的规模；n0为一阈值，表示当问题P的规模不超过n0时，问题已容易直接解出，不必再继续分解。ADHOC(P)是该分治法中的基本子算法，用于直接解小规模的问题P。因此，当P的规模不超过n0时，直接用算法ADHOC(P)求解。算法MERGE(y1,y2,.,yk)是该分治法中的合并子算法，用于将P的子问题1 ,P2 ,.,Pk的相应的解y1,y2,.,yk合并为P的解。经过上面的分析，我们应该考虑原问题分多少个子问题才较适宜？各个子问题的规模应该怎样才为适当？这些问题很难予以肯定的回答。但大量实践发现，在用分治法设计算法时，最好使子问题的规模大致相同。许多问题可以取k=2，又称二分法，大家熟悉

5、的二分查找，快速排序，归并排序都是基于这种算法的应用。五、算法的应用下面我再例谈几个问题，以帮助大家能够彻底地掌握这种算法。【例2】循环比赛【问题描述】设有n支(n=2m,m=2）表示第i个队员在第j-1天的比赛对手。仔细观察发现这张表是中心对称的，这给我们一个启示，我们要设计一张88的比赛安排表a1.8,1.8，只需要设计出表的上半部分，即两张44的安排表a1.4,1.4和a1.4,5.8即可。之后，通过已经设计出来的表的左上角a1.4,1.4复制出表的右下角a5.8,5.8，通过右上角a1.4,5.8制出表的左下角a5.8,1.4。同样，任一张44的比赛安排表可以通过两张22的比赛安排表产

6、生。继续直到两张11的比赛安排表，这是问题的最小规模，即可赋初值解决。根据分析的规律，这完全符合分治算法。【方法一】采用递归结构，完整程序如下：Program ex2;type arr=array1.1000,1.1000 of integer;var a:arr;i,j,m,n:integer;procedure arrange(var a:arr;n,left,right:integer);n表示方阵的大小，即球队的数量 var i,j,mid:integer;begin if n2 then exit; mid:=(left+right) div 2;把方阵分为两半 n:=n div 2

7、; arrange(a,n,left,mid);递归处理左上角方阵 arrange(a,n,mid+1,right);递归处理右上角方阵 for i:=1 to n do begin for j:=left to mid do ai+n,j+n:=ai,j; 从已得方阵的左上角推出右下角 for j:=mid+1 to right do ai+n,j-n:=ai,j; 从已得方阵的右上角推出左下角 end;end;begin readln(m); n:=1; for i:=1 to m do n:=n*2; fillchar(a,sizeof(a),0); for i:=1 to n do a

8、1,i:=i;先确定第一行球队的编号 arrange(a,n,1,n);递归产生各个方阵 for i:=1 to n do begin for j:=1 to n do write(ai,j:5); writeln; end;end.【方法二】采用非递归结构，核心程序段如下：procedure arrange(var a:arr;max:integer); max表示方阵的大小，即球队的数量 var i,j,k,n,left,right,mid:integer;begin n:=2; while n=max do 依次安排2、4、8支球队 begin left:=1;left当前被按排球队的左

9、边界 while leftmax do begin right:=left+n-1; right当前被按排球队的右边界 mid:=(left+right) div 2; k:=n div 2; 将球队分成左右两半处理，每半有k个球队 for i:=1 to k do begin for j:=left to mid do ai+k,j+k:=ai,j; 由左上角推出右下角 for j:=mid+1 to right do ai+k,j-k:=ai,j; 由右上角推出左下角 end; left:=left+n; end; n:=n*2; end;end;通过上例我们得出分治算法可以使用递归结构和

10、非递归结构解决，非递归编写的程序时间、空间复杂度低，而递归编写的程序具有容易设计，结构清晰，可读性强等优点。 【例3】贷款利率【问题描述】当一个人从银行贷款后，在一段时间内他(她)将不得不每月偿还固定的分期付款。这个问题要求计算出贷款者向银行支付的利率。假设利率按月累计。【输入】输入文件仅一行包含三个用空格隔开的正整数。第一个整数表示贷款的原值a，第二个整数表示每月支付的分期付款金额b，第三个整数表示分期付款还清贷款所需的总月数m。(1a,b109,1m104)【输出】输出文件应该是一个实数，表示该贷款的月利率(用百分数表示)，四舍五入精确到0.1%。【样例输入】1000 100 12【样例输

11、出】2.9【分析】显然这是一道数学题，假设月利率为x，f(x)=，求解这个一元高阶方程，考虑到时间复杂度，采用穷举法似乎不太可行。联想noip2001复赛提高组第一题一元三次方程求解，我们采用的是分治法，这题的思路就来了。我们可以先确定月利率的大致区间x1.x2，然后将该区间分成左右两个子区间：左子区间x1.xm，右子区间xm.x2（其中xm=）。如果f(xm)0，假设的月利率就低了，x1就调整为xm；否则x2调整为xm上述对分过程一直进行到abs(x1-x2)=1e10为止，此时可以确定x1为f(x)的根。源程序参考如下： program ex3; var a,b,m:longint; xm

12、,x1,x2,xu:extended;function mi(x:extended):extended; var i:longint; t:extended; begin t:=1; for i:=1 to m do t:=t*x; mi:=t; end; beginread(a,b,m); if a=b*m then begin writeln(0.0);halt;end; x1:=1; x2:=2; xu:=mi(x2); while a*xu-b*(1-xu)/(1-x2)1e-10 do begin xm:=(x1+x2)/2 ; xu:=mi(xm); if a*xu-b*(1-xu

13、)/(1-xm) 1 do begin nl:=nl div 3;把数据平均分成三组 s1:=0;s2:=0;for i:=k+1 to k+nl do s1:=s1+ai; for i:=k+nl+1 to k+2*nl do s2:=s2+ai;分别求前两组数据和if s1max then max:=ai; If ai2）个数据，先分成两组，分别求其最大值、最小值，然后分别将这两组的最大值、最小值相比较，求出全部元素的最大值和最小值。若分组后元素个数仍大于2，则再次分组，直至组内元素小于等于2。 下面我们通过具体程序，对该算法作进一步阐述。算法通过调用一个maxmin(n,n,max,mi

14、n)的递归过程来从已知n个元素的集合a中找出最大值max和最小值min。数组a表示集合，元素个数用n表示。若a=2，则它们分别为max和min，而max1，max2，min1，min2分别来存放两个子集的最大值和最小值。下面是完整的参考程序：Program ex5;Var n,i:integer;max,min:real;a:array1.100 of real;Procedure maxmin(i,j:integer;var max,min:real); Var mid:integer;max1,max2,min1,min2:real;Begin Case j-I of 0:begin ma

15、x:=ai;min:=aj;end; 集合中只有一个元素 1:if aimax2 then max:=max1 else max:=max2; 归并 If min1min2 then min:=min2 else min:=min1; End; End;End;begin readln(n); for i:=1 to n do read(ai); maxmin(1,n,max,min); writeln; writeln(max number is,max, ;,min number is,min);end.【例6】一元三次方程求解(noip2001提高组复赛第一题)【问题描述】有形如：ax3

16、+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 -4 20【样例输出】-2.00 2.00 5.00【算法分析】此题可以用枚举法求解，但如果求解的精度进一步提高，使用枚

17、举法就无能为力了，在此我们讨论如何用二分法求解此题。由题意知（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，xx和右子区间xx，x2（其中xx=（x1+x2）/2）。如果f(x1)*f(xx)0，则确定根在左区间x1，xx内，将xx设为该区间的右界值（x2=xx），继续对

18、左区间进行对分；否则确定根在右区间xx，x2内，将xx设为该区间的左界值（x1=xx），继续对右区间进行对分；上述对分过程一直进行到区间的间距满足精度要求为止（即x2-x10.005）。此时确定x1为f(x)的根。参考程序如下：Program ex6;$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

19、(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.【例7】数的查找【问题描述】对于给定的n个元素的数组a1.n，要求从中找出第k小的元素。【输入】第一行是总数n和k，第二行是n个待比较的元素。【输出】第k小的数在数组中的位置。【样例输入】10 47 2 6 8 13 15 11 22 10 9【样例输出】8【问题

20、分析】对于一组混乱无序的数来说，要找到第k小的元素通常要经过两个步骤方可实现：第一步，将数进行从小到大排序；第二步，确定第k个位置上的数。传统的排序算法（插入排序法、选择排序法等）大家已经非常熟悉了，但已学过的排序方法无论从速度上，还是从稳定性方面不是最佳的，因此在实际运用中一般不大采用。事实上用归并排序或堆排序的方法来实现排序相对而言是较快较稳的，或者通过避免排序的方法同样也可以有效地提高查找的效率。下面戯一列由10个元素组成的数组：7 2 6 8 13 15 11 22 10 9假设要找出k=4的元素，我们不妨这样来处理：设i指针为这个数列的左边界，j指针为这个数列的右边界，将中间数13作

21、为一个基准数，然后i指针从左边扫描过来，碰到大于等于13时停止，再让j指针从右边扫描过来，碰到小于等于13时停止，如果ij，此时13小的数在左边，比13大或相等的数在右边，即变成二段7 2 6 8 9 10 1122 15 13观察一下，比第二段小的数有7个，题目要求k=4，那么我们就可以将数的搜索范围缩小到第一段。递归地对第一段进行上述处理，变成了7 2 6 8 9 10 11三段。 通看一遍，第一段右边界是，而第二段的左边界是5，而基准数8正好是第4小的元素。这个方法正是利用了分治算法，时间复杂度应该是log2(n)，下面是核心程序段：function find(l,r,k:longint

22、):longint;var i,j,mid:longint;begin if l=r then exit(al); i:=l; j:=r; mid:=a(i+j)div 2; repeat while aimid do dec(j); if ij; if (l=j) and (k=j) then exit(find(l,j,k); if (i=i) then exit(find(i,r,k); exit(mid);end;【例8】旅行家的预算(noip1999提高组复赛第三题)【问题描述】一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是空的）。给定两个城市之间的距离A、

23、汽车油箱的容量C（以升为单位）每升汽油能行驶的距离B、出发点每升汽油价格P和沿途油站数N（0=N=100），油站i离出发点的距离Di、每升汽油价格Pi（il，2，.N）。计算结果四舍五入至小数点后两位。如果无法到达目的地，则输出“No solution”。【输入】A C B P N D1 P1 D2 P2 DN PN【输出】最小费用【样例输入】275.6 11.9 27.4 2.8 2102.0 2.9220.0 2.2【样例输出】26.95【算法分析】（1）第i站到第i+1站的距离大于C*B，则输出无解信息后退出。（2）有解的话我们这样考虑，除终点站外从后向前寻找油价最低的加油站k，如果k不

24、是起点，显然车至k站油箱应为空，利用分治法可以将起点至k站、k站至终点作为两个子问题考虑；否则k为起点，若能一次加油即到达终点则直接计算，若不能则在k站应加满油，然后从后往前寻找除起点终点站外油价最低的加油站，若该加油站位于起点加满油后不能到达之处，则到达该站时油箱应该为空，以该站为界将全程分为两个子问题考虑，否则该加油站处于起点加满油后能到达之处，前一段可直接计算费用，后一段又可视为一个有余油的子问题。对每个子问题继续用上面分治的算法解决。（3）设计一个递归函数money，形式参数start表示起点站，形式参数stop表示终点站，形式参数rest表示到达加油站start时汽车油箱余下的油的容

25、量，它的功能是最终计算出从加油站start到stop区间内的最小费用。 参考程序代码如下：function money (start，stop:longint；rest:real):real；Var k:longint；beginif stop-start=1 then money:=(dstop-dstart)/d2-rest)*pstartelse begin k:=minp(start，stop-1)； minp(b，e:longint):longint；在b站到e站之间从后往前找油价最低的站 if kstart 油价最低的加油站不是起点站 then money:=money(start

26、，k，rest)+money(k，stop，0) else if dstop-dstart=d2*c 在起点加满油能直接到达该段终点 then money:=(dstop-dstart)/d2-rest) * pstart else begin k:=minp(start+1 , stop-1) ; if dk - dstart = d2 * c then 在起点加满油能到达加油站k money:=(c-rest) * pstart + money(k, stop, c-(dk - dstart)/d2) else money := money(start, k, rest) + money(

27、 k, stop, 0) end endend;【例9】坐车【问题描述】甲、乙两人同时从A地出发尽快同时赶到B地，出发时你在A地开着一辆只能坐两个人的小车，又知甲乙两人步行的速度，问，怎样利用小车才能使两人尽快同时到达。【算法分析】最佳方案：甲先乘车到达C地后下车行走，车回头接已经走到E地的乙设在D相遇，乙乘车到达B地时也步行到达，这时时间最短。问题转化为求C点的位置，设A、B距离为S，步行速度为a，车速为b，甲耗时T1，乙耗时T2。【关键算法】1）c0:=0;c1:=s;,c:=(c0+c1)/2;以中间点作为测试数据；2）求T1，T2;3）if T1T2 then C0、C中点设为C el

28、se 把C、C1中点设为C。反复进行（2）（3）直到T1-T2e(误差)参考程序repeat c:=(c0+c1)/2; t3:=c/b;计算甲乘车到c的时间 t1:=t3+(s-c)/a;计算甲总耗时 t4:=（c-t3*a）/(a+b)计算小车从c回头与乙相遇的时间 t2:=t3+t4+(s-(t3+t4)*a)/b;计算乙总耗时； if t1t2 then c1:=c else c0:=c;until abs(t1-t2)e0;(e0是一个足够小的数)【例10】剔除多余括号 【问题描述】输入一个含有括号的四则运算表达式，可能含有多余的括号，编程整理该表达式，去掉所有多余的括号，原表达式中

29、所有变量和运算符相对位置保持不变，并保持与原表达式等价。 输入表达式应输出表达式a+(b+c)a+b+c(a*b)+c/(d*e)a*b+a/(d*e)a+b/(c-d)a+b/(c-d)例如：注意输入表达式以字符串输入，长度不超过255，输入不需要判错。所有变量为单个小写字母。只是要求去掉所有多余括号，不要求对表达式简化。【样例输入】(a*b)+c/da*b+c/d【样例输出】a*b+c/da*b+c/d【算法分析】四则运算表达式含运算符+,-,*,/,(,)，我们分析一下表达式中哪些括号可以去掉。设待整理的表达式为（s1 op s2）；op为括号内优先级最低的运算符（“+”，“-”或“*”

30、，“/”）；左邻括号的运算符为“/”，则括号必须保留，即 /（s1 op s2） 形式。左邻括号的运算符为“*”或“-”。而op为“+”或“-”，则保留括号，即*（s1+s2） 或 -（s1+s2） 或 *（s1-s2） 或 -（s1-s2）右邻括号的运算符为“*”或“/”，而op为“+”或“-”，原式中的op运算必须优先进行，因此括号不去除，即（s1+s2）* 除上述情况外，可以括号去除，即 s1 op s2 等价于（s1 op s2）在设计算法时，可以在优先级最低的运算符处将原表达式拆分为两个子表达式，然后对每个子表达采用相似的方法进行拆分，同时对相应层进行括号整理，直至最外层的括号保留或

31、去除为止。例如，剔除表达式“(a+b)*f)-(i/j)”中多余的括号。依据上述算法进行拆分整理过程如下：最后自底向上得到整理结果：(a+b)*f-i/j。参考程序如下：var ch:char;expr:string;function rightbracket(s:string;i:byte):byte;var q:byte;begin q:=1; repeat inc(i); if si=( then inc(q) else if si=) then dec(q); until q=0; rightbracket:=i;end;function find(s:string):byte;var

32、 i,k,k1,k2:byte;begin i:=1;k1:=0;k2:=0; while i=length(s) do begin if (si=+)or(si=-) then k1:=i; if (si=*)or(si=/) then k2:=i; if si=( then i:=rightbracket(s,i); inc(i); end; if k1=0 then find:=k2 else find:=k1;end;function deletebracket(s:string;var p:char):string;var i:byte;ch1,ch2:char;left,right

33、:string;begin if length(s)=1 then begin deletebracket:=s;p:= ;exit;end; if (s1=()and(rightbracket(s,1)=length(s) then begin deletebracket:=deletebracket(copy(s,2,length(s)-2),p); exit; end; i:=find(s); p:=si; left:=deletebracket(copy(s,1,i-1),ch1); right:=deletebracket(copy(s,i+1,length(s)-i),ch2);

34、if (p in *,/)and(ch1 in +,-) then left:=(+left+); if (p in *,-)and(ch2 in +,-) or (p=/)and(ch2 ) then right:=(+right+); deletebracket:=left+p+right;end;begin readln(expr); writeln(deletebracket(expr,ch);end.【例11】导线和开关【问题描述】如下图是一个具有3根导线的电缆把A区和B区连接起来。在A区3根导线标以1，2，3;在B区导线1和被连到开关3，导线2连到开关1。一般说来，电缆含(190)

35、根导线，在A区标以1,2,m。在B区有个开关，标为1，2，。每一根导线都被严格地连到这些开关中的某一个上; 每一个开关上可以连有0根或多根导线。你的程序应作某些测量来确定导线和开关怎样连。每个开关或处于接通或处于断开状态，开关的初始状态为断开。我们可用一个探头P在A区进行测试：如果探头点到某根导线上，当且仅当该导线连到处于接通状态的开关时，灯L才会点亮。你的程序从标准输入读入一行以得到数字m；然后可以通过向标准输出写入一行以发出命令(共3种命令)。每种命令的开头是一个大写字母:测试导线命令T：T后面跟一个导线标号；改变开关状态命令C：C后面跟一个开关标号；完成命令D：D后面跟的是一个表列，该表

36、列中的第i个元素代表与导线i相连的开关号。在命令T和C之后，你的程序应从标准输入读入一行。若开关状态能使灯亮，则命令T的回答应是Y；反之，回答应是N。命令C的作用是改变开关的状态(若原来是接通则变为断开；若原来是断开则变为接通)。对C命令的回答是作为一种反馈信号。 你的程序可以给出一系列命令，将T命令与C命令以任意顺序混合使用。最后给出命令D，并结束。你的程序给出的命令总数应不大于900。举例：下表给出了一个实例，对应于上图，这是一个有8条命令的对话。 Standard Output Standard Input 3 C 3 Y T 1 Y T 2 N T 3 Y C 3 N C 2 Y T

37、2 N D 3 1 3 【算法分析】为了使导线和开关的连接工作有规律地进行，我们不妨采用二分法。1分解设当前待接的开关为head.tail,初始时为1.m,则左区间head.(head+tail-1)/2,开关集合为p1=1.m，右区间 (head+tail-1)/2+1.tail,开关集合为p2=，导线的连接状态state=(0,1)，分别表示断开和连接，对区间进行检测，对p1中的每根导线发出T命令，若开关状态为闭合，且回答N,或者开关状态为断开，且回答Y,则移到p2。2递归过程check(p1,左区间,1-state)check(p2,右区间,state)3合并当区间仅剩下一个开关(hea

38、d=tail)且与之相连的导线集合p1非空，则p1中所有的导线与head相连,并使得ANSi=head,i属于p1算法框架Procedure check(p1,head,tail,state);Begin if p1 then if head =tail then begin 计算左区间p1；通过c命令和用户应答，将左区间开关状态取反；右区间p2=；对p1中的每根导线发出T命令，若开关状态为闭合，且回答N,或者开关状态为断开，且回答Y,则移到p2； end;i:=trunc(head+tail)/2);check(p1,head,i,state);check(p2,i+1,tail,state

39、);End;【例12】最接近点对问题【问题描述】在应用中，常用诸如点、圆等简单的几何对象代表现实世界中的实体。在涉及这些几何对象的问题中，常需要了解其邻域中其他几何对象的信息。例如，在空中交通控制问题中，若将飞机作为空间中移动的一个点来看待，则具有最大碰撞危险的2架飞机，就是这个空间中最接近的一对点。这类问题是计算几何学中研究的基本问题之一。下面我们着重考虑平面上的最接近点对问题。最接近点对问题的提法是:给定平面上n个点，找其中的一对点，使得在n个点的所有点对中，该点对的距离最小。严格地说，最接近点对可能多于1对。为了简单起见，这里只限于找其中的一对。（预备知识：在平面几何中每一个点都用（x,

40、y）来表示它在平面中的位置，点1（x1,y1）与点2（x2,y2）之间的距离可用公式：表示）输入：平面中各点的坐标，以(0,0)表示输入结束。输出：距离最近的两点坐标。样例输入：7 2 2 7 3 4 9 7 0 0样例输出：the nearest length is:3.16 The first point is:2 2.00 7.00 The second point is:3 3.00 4.00问题分析：常规分析中，我们通常是套用公式，求出所有点对之间的距离，然后用找最小值的方法进行比较分析，从而找出距离最小的点对。这种方法称为直接分析法。使用这种方法优点在于能找出所有的点对，比较稳定；

41、缺点在于耗时太多，用数学方法分析一下，我们就会发现对于平面上的n个点，会产生n*(n-1)个点对，即需要求n*(n-1)次距离，就时间复杂性而言应为o(n2)。对于n的值很小的时候可以这样做，但随着n值增大，计算机所花的计算时间将成倍地增加，很显然这种算法是不可取的。不妨试着将大问题规模缩小，将一个大问题缩小为两个小问题，其中一个问题（称为问题A）大小为n/2，另一个问题（称为问题B）大小也为n/2。这样出现最近点对的情况有可能是以下三种：情况1:两个点都出现在A中；情况2:两个点都出现在B中；情况3:一个点在A中，一个点在B中。分别找出这三种情况下的距离最近的点对，而最近的点对必定是这三种情

42、况下距离值最小的。对于情况1和情况2都可以递归地实现找距离最近的点对，对于情况3则需用另外的方法进行判断。这种方法取决于如何对A和B进行划分，一种合理的方法是在根据X坐标的中间值处做一条垂线，垂线的左边归点集A，垂线的右边归点集B，在垂线线上点可以A，B之间分配以便满足A，B的大小。因为对于A中的任意一个点P，B中仍需用要n/2个点与之构成候选点，这样的思路势必会导致耗时仍为o(n2)，因此我们应该把注意力转移到情况3上去。为了使问题易于理解和分析，我们先来考虑一维的情形。如下图所示，x轴上的n个实数x1,x2,xn。那么找最接近点对就是为这n个实数中相差最小的2个实数。我们显然可以先将x1,

43、x2,xn排好序，然后，用一次线性扫描就可以找出最接近点对，这种方法主要计算时间花在排序上，虽然这种方法无法适应二维的情形，但是如果我们对这种一维的简单情形试用分治法来求解，那么就有可能推广到二维的情形。BmAP3P2Q3Q1Q2P1根据某一种方法，我们找出了划分两个子集的分割点m，假设已经找到A集中的最小点对距离为s1，B集中的最小点对距离为s2，又设在两种情况下的最小点对距离为g，显然，g=min(s1,s2)。而第三种情况（即跨越两个子集）只需找出s1中坐标的最大值点p3和s2中坐标的最小值点q3，然后求出p3和q3之间的距离，可以得出g最终应是s1,s2，q3-p3的最小值。通过分治算法，我们可以把时间复杂度降低到o(n)。至此，问题的关键转化为如何确定分割点m及A和B两个数集的划分。明显地，如果通过m点，将两个数集的规模划分相等无疑是最佳的。涉及的数据为x:array1.50 of real;存放点的坐标程序分