致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。 分治法所能解决的问题一般具有以下几个特征：
1. 该问题的规模缩小到一定的程度就可以容易地解决；
2. 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。 3. 利用该问题分解出的子问题的解可以合并为该问题的解；
4. 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。 上述的第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加；第二条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用；第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑用贪心法或动态规划法。第四条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法较好。
8. 2 分治法解题的步骤 分治法的基本步骤
分治法在每一层递归上都有三个步骤：
1. 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题； 2. 解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题； 合并：将各个子问题的解合并为原问题的解。 例1.：【问题描述】
设有N选手的循环比赛，其中N=2m，要求每名选手要与其他N-1名选手都赛一次。每名
选手每天比赛一次，循环比赛共进行N-1天，要求每天没有选手轮空。
【输入】： m 【输出】：表格形式的比赛安排表 【样例输入】： 3 【样例输出】：
１ ２ ３ ４ ５ ６ ７ ８ ２ １ ４ ３ ６ ５ ８ ７ ３ ４ １ ２ ７ ８ ５ ６ ４ ３ ２ １ ８ ７ ６ ５ ５ ６ ７ ８ １ ２ ３ ４ ６ ５ ８ ７ ２ １ ４ ３ ７ ８ ５ ６ ３ ４ １ ２ ８ ７ ６ ５ ４ ３ ２ １
【分析】：从八位选手的循环比赛表中可以看出，这是一个具有对称性的方阵，可以把方阵一分为四来看，那么左上角的4*4的方阵就是前四位选手的循环比赛表，而右上角的4*4的方阵就是后四位选手的循环比赛表，它们在本质上是一样的，都是4个选手的循环比赛表，所不同的只是选手编号不同而已，将左上角中方阵的所有元素加上4就能得到右上角的方阵。下方的两个方阵表示前四位选手和后四位选手进行交叉循环比赛的情况，同样具有对称性，将右上角方阵复制到左下角即得到1，2，3，4四位选手和5，6，7，8四位选手的循环比赛表，根据对称性， 右下角的方阵应与左上角的方阵相同。这样，八名选手的循环比赛表可以由四名选手的循环比赛表根据对称性生成出来。同样地， 四名选手的循环比赛表可以由二名选手的循环比赛表根据对称性生成出来,而两名选手的循环比赛表可以说是已知的,这种程序设计方法叫做分治法,其基本思想是把一个规模为n的问题分成若干个规模较小的问题,使得从这些较小问题的解易于构造出整个问题的解。 程序中用数组matchlist记录n名选手的循环比赛表, 整个循环比赛表从最初的1*1的方阵按上述规则生成出2*2 的方阵, 再生成出4*4 的方阵,……
- 16 -
program fenzhi;
const maxn=32;maxm=5; var
i,j,k,m,n,half:integer;
matchlist:array [1..maxn,1..maxn] of integer; begin
write('Input m:'); readln(m); n:=1;
for i:=1 to m do n:=n*2; k:=1;
matchlist[1,1]:=1; half:=1;
while k<=m do begin
for i:=1 to half do {构造右上角方阵} for j:=1 to half do
matchlist[i,j+half]:=matchlist[i,j]+half;
for i:=1 to half do {对称交换构造下半部分方阵} for j:=1 to half do begin
matchlist[i+half,j]:=matchlist[i,j+half]; matchlist[i+half,j+half]:=matchlist[i,j] end;
half:=half*2; k:=k+1 end;
for i:=1 to n do begin
for j:=1 to n do
write(matchlist[i,j]:4); writeln end; end.
例2.：数的查找 【问题描述】
对于给定的n个元素的数组a[1..n]。要求从中找出第k小的元素。 【输入】：
第一行是总数n和k，第二行是n个待比较的元素/ 【输出】：
第k小的数在数组中的位置 【样例输入】 5 3
23 8 91 56 4 【样例输出】 1
数据范围：1<=n<=100000000 【问题分析】：
对于一组混乱的数据来说，要找到第k小的元素，通常要经过两个步骤就可以实现： 第一步：将数进行排序；
- 17 -
第二步：确定第k个位置上的数即可。 传统的排序算法基本上已经学过了，但是从速度和稳定性上不是最佳的，故此在实际运用中一般不大采用。那么我们可以考虑用分治算法来分析：
比如有10个数据元素组成的数组： [ 7 2 6 8 10 1 6 22 9 4 ]
假设我要找k=3的元素，将7作为一个参照数，将这个元素比7小的数放在7的左边，比七大的或相等的数放在7的右边，这样我们可以得到第一次数组的调整： [ 4 2 6 6 1 ] 7 [ 10 22 9 8]
观察一下，比7小的数有5个，那么7应该是该数组中的第6个小的元素。题目要求k=3，那么我们就应该将数的搜索范围缩小到7的左边，以4为参照数，确定4的实际位置为：
[1 2 ] 4 [ 6 6 ]
通看一遍，应该是第3小的元素，正是题目所要找的数。 【参考程序】： program sort; var i,k,n:integer;
a,c:array[1..100000000] of integer; procedure search(b,e:integer); var i,j,m,t:integer; begin
if b=e then exit; {相等无解或已找完} i:=b;{标志位} j:=e; m:=a[k]; repeat
while a[i]
if i=k then exit; {标志位与要找的数相等}
if j>k then search(b,j) {找前面} else search(j+1,e) {找后面} end; begin
readln(n,k);
for i:=1 to n do begin read(a[i]);{读入} c[i]:=i;{置序号} end; search(1,n);
write(c[k]); {输出序号} end.
例3.：乘车问题 【问题描述】
甲、乙两人同时从A地出发要尽快同时赶到B地。出发时A地有一辆小车，可是这辆小车除了驾驶员外只能带一人。已知甲、乙两人的步行速度一样，且小于小车的速度。问：怎么样利用小车才能使两人尽快同时到达目的地。 【问题输入】
仅一行，三个数据分别表示AB两地的距离s，人的步行速度a，车的速度b。 【问题输出】
两人同时到达B地需要的最短时间。
- 18 -
【输入输出样例】 car.in
120 5 25 car.out
9.6000000000E+00 【小车问题分析】：
最佳方案为：甲先乘车到达k处后下车步行，小车再回头接已走到c处的乙，在d处相遇后，乙再乘车赶往b，最后甲、乙一起到达b地。如下图所示，这时所用的时间最短。这样问题就转换成了求k处的位置，我们可以用二分法，不断尝试，直到满足同时到达的时间精度。
算法框架如下“ 1、输入s,a,b;
2、c0:=0; c1:=s; c:=(c0+c1)/2; 3、求t1,t2;
4、如果t1 反复执行3和4，直到abs(t1 s,a,b,c,c0,c1,t1,t2,t3,t4:real; begin assign(input,?car.in?); assign(output,?car.out?); reset(input); rewrite(output); readln(s,a,b); c0:=0; c1:=s; repeat c:=(c0+c1)/2; t3:=c/b; t1:=t3+(s-c)/a; t4:=(c-t3*a)/(a+b); t2:=t3+t4+(s-(t3+t4)*a)/b; if t1 【深入思考】 - 19 - 现在把上述问题修改一下，已经A，B两地相距S=100公里，在A地有n个人，现在有一辆汽车，此汽车除司机外只能载一人，已知汽车的速度为V1=50公里/小时，人的速度为V2=5公里/小时。要求设计一种方案，使得最后一个人用最少的时间到达B。 例4.：再谈乘车问题 【问题描述】： AB两地的距离是s公里，甲、乙、丙三人从A到B共同完成任务。从A地出发时，A地有X，Y两种出租车可供使用，已知三人步行的速度为V1，出租车Y速度为V2，并仅能载一人，出租车X的速度为V3，能载两人。问题是从A地出发时X只能载一人，回头接人时才能载两人，试问怎么样安排行程，才能使甲、乙、丙三人尽快同时到达B后共同完成任务（已知V1 ①、 从问题可以看出，要尽快同时到达B，则甲、乙、丙需要充分利用X，Y两种出租车； ②、 利用下列图示可以说明安排的方法： ③、 假设C点表示出租车X先载一人（设甲）的下车点，然后回头接乙、丙相遇于D点； ④、 D点表示出租车Y先载人（设乙）到E点下车，回头接丙相遇于G点，再回头追到 乙于D点，这时出租车X正好到达D点。 ⑤、 由此可以看出，甲乘车到C，从C步行到B；乙乘Y车到E，然后步行到D，再从D 乘X车到达B；丙步行到G，被出租车Y接到D点会同乙乘出租车X到达B。 【分治算法】： 假设取AB的中点作为出租车X载甲的下车点，计算结果若甲先达到B，则实验点用折半方法往出发点靠，反之若乙丙先到达B则，甲的下车点要向B靠，即在接近B的一半求新的实验点。这里设出发点到甲下车点的距离为L。 当确定甲下车点C后（试探），接着用同样的方法测试D点位置，此时测试区域为AC，确定点为D。 在C，D测试点确定后，再用二分方法对区间AD试探乙乘出租车Y的下车点E。 误差值要求e=0.001. 【参考程序】： const e=0.001; var .... begin readln(s,a,b,c);{c>b>a} c0:=0; c1:=s; repeat l:=(c0+c1)/2; d0:=0; d1:=l; repeat m:=(d0+d1)/2; e0:=0; e1:=m; repeat ee:=(e0+e1)/2; tae:=ee/b; - 20 -