JSOI2007夏令营讲义 Page 1 of 15
分治法
一、引入
有一个找伪币的问题，说给你一个装有16个硬币的袋子，16个硬币中有一个是伪造的，并且那个伪造的硬币比真的硬币要轻一些。你的任务是找出这个伪造的硬币。为了帮助你完成这一任务，将提供一台可用来比较两组硬币重量的仪器，利用这台仪器，可以知道两组硬币的重量是否相同。
方法很简单，如先比较硬币1与硬币2的重量，假如硬币1比硬币2轻，则硬币1是伪造的，假如硬币2比硬币1轻，则硬币2是伪造的，假如两硬币重量相等，则说明1和2都不是伪造的，则再比较硬币3和硬币4，??，按照这种方式，可以最多通过8次比较来判断伪币的存在并找出这一伪币。
另外一种方法就是利用二分的思想。假如把16硬币的例子看成一个大的问题。第一步，把这一问题分成两个小问题。随机选择8个硬币作为第一组称为A组，剩下的8个硬币作为第二组称为B组。第二步，判断伪币在A组还是在B组中，如果在A组中，则再把A组中的8个硬币随机分成2组，每组4个再去比较，??，这样4次一定能找出伪币。
还可以用三分的思想解决，把16个硬币分成3组（A组5个、B组5个、C组6个），称一次判断出伪币在A、B、C哪一组中，假如在C组中，则再把C组中的6个分成3组（2个、2个、2个），称一次判断出在哪一组，然后再称1次就能找出伪币，这样最多称3次便能找出。
二、基本概念
分治法是将一个难以直接解决的大问题，分解成k个规模较小的相互独立的、相同（类似）子问题，以便各个击破，分而治之的策略，即“分而治之”的意思。最常见的就是二分法（k=2）。而且根据平衡子问题的思想一般把问题分解成k个规模相等的子问题。
N
一些基本的题目如：归并排序、快速排序、二分查找、2个人的循环比赛表等。
分治法是程序设计中常见的考虑和处理问题的方法，其特点主要有以下两个： （1）对大问题的解决可以分解成对若干小问题的解决；
（2）每个小问题出现的情况又与大问题出现的情况是一致的。
在算法实现中，我们通常采用递归来实现。当然有的问题在分析时用的是递归的思路，在具体实现时只用递推的方法，这样做的目的是简化运行步骤，提高运行效率。
分治法在每一层递归上都要有三个步骤：
（1）分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题； （2）解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题； （3）合并：将各个子问题的解合并为原问题的解。
三、应用举例
例1、快速排序 [问题分析]
设N个元素A[1..N]，要求按非递减排序。
选择某一个元素X（一般取中间那个，初始时设i=1,j=N,则X=a[（i+j） div 2]），从
JSOI2007夏令营讲义 Page 2 of 15
两头(A[i]、A[j])开始逐个与X比较，找到左边比它大的那个元素A[i]和右边比它小的那个元素A[j]，则交换A[i]与A[j] ，一举两得，然后inc(i)、dec(j)再继续进行，直到i>j。则这一趟结束，效果是X一定排在了它应该在的位置上了。
然后，对X左右两边的部分进行类似的递归操作。实际上是一种二分思想，即把大于某个数的所有数交换到它的右边，而把小于它的数都交换到左边。如此这般递归下去，直到都符合要求为止。
[参考程序]
program quicksort; const max = 10;
var a:array[1..max] of longint; i:longint;
procedure qsort(l,r: longint); var i,j,x,y: longint; begin
i:=l;j:=r;
x:=a[(l+r) div 2]; repeat
while a[i] y:=a[i]; a[i]:=a[j]; a[j]:=y; inc(i); dec(j); end; until i>j; if l begin randomize; for i:=1 to max do begin a[i]:=random(1000);write(a[i]:6);end; JSOI2007夏令营讲义 Page 3 of 15 writeln; qsort(1,max); for i:=1 to max do write(a[i]:6); readln; end. 例2、循环比赛日程表（match.???） 设有n个选手的循环比赛，其中n=2，要求每名选手要与其他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表示当前方阵的大小,也是要生成的下一个方阵的大小的一半. [参考程序] program match; 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; m JSOI2007夏令营讲义 Page 4 of 15 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. [样例] Input m: 4 Output: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 2 1 4 3 6 5 8 7 10 9 12 11 14 13 16 15 3 4 1 2 7 8 5 6 11 12 9 10 15 16 13 14 4 3 2 1 8 7 6 5 12 11 10 9 16 15 14 13 5 6 7 8 1 2 3 4 13 14 15 16 9 10 11 12 6 5 8 7 2 1 4 3 14 13 16 15 10 9 12 11 7 8 5 6 3 4 1 2 15 16 13 14 11 12 9 10 8 7 6 5 4 3 2 1 16 15 14 13 12 11 10 9 9 10 11 12 13 14 15 16 1 2 3 4 5 6 7 8 10 9 12 11 14 13 16 15 2 1 4 3 6 5 8 7 11 12 9 10 15 16 13 14 3 4 1 2 7 8 5 6 12 11 10 9 16 15 14 13 4 3 2 1 8 7 6 5 13 14 15 16 9 10 11 12 5 6 7 8 1 2 3 4 14 13 16 15 10 9 12 11 6 5 8 7 2 1 4 3 15 16 13 14 11 12 9 10 7 8 5 6 3 4 1 2 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 例3、小车问题（car.???） [问题描述] 甲、乙两人同时从A地出发要尽快同时赶到B地。出发时A地有一辆小车，可是这辆小车除了驾驶员外只能带一人。已知甲、乙两人的步行速度一样，且小于车的速度。问：怎样
