分治法的合并步骤是算法的关键所在。有些问题的合并方法比较明显，有些问题合并方法比较复杂，或者是有多种合并方案；或者是合并方案不明显。究竟应该怎样合并，没有统一的模式，需要具体问题具体分析。
【问题】 大整数乘法
问题描述：
通常，在分析一个算法的计算复杂性时，都将加法和乘法运算当作是基本运算来处理，即将执行一次加法或乘法运算所需的计算时间当作一个仅取决于计算机硬件处理速度的常数。
这个假定仅在计算机硬件能对参加运算的整数直接表示和处理时才是合理的。然而，在某些情况下，我们要处理很大的整数，它无法在计算机硬件能直接表示的范围内进行处理。若用浮点数来表示它，则只能近似地表示它的大小，计算结果中的有效数字也受到限制。若要精确地表示大整数并在计算结果中要求精确地得到所有位数上的数字，就必须用软件的方法来实现大整数的算术运算。
请设计一个有效的算法，可以进行两个n位大整数的乘法运算。
设X和Y都是n位的二进制整数，现在要计算它们的乘积XY。我们可以用小学所学的方法来设计一个计算乘积XY的算法，但是这样做计算步骤太多，显得效率较低。如果将每2个1位数的乘法或加法看作一步运算，那么这种方法要作O(n2)步运算才能求出乘积XY。下面我们用分治法来设计一个更有效的大整数乘积算法。
图6-3 大整数X和Y的分段
我们将n位的二进制整数X和Y各分为2段，每段的长为n/2位（为简单起见，假设n是2的幂），如图6-3所示。
由此，X=A2n/2+B，Y=C2n/2+D。这样，X和Y的乘积为：
XY=(A2n/2+B)(C2n/2+D)=AC2n+(AD+CB)2n/2+BD （1）
如果按式（1）计算XY，则我们必须进行4次n/2位整数的乘法(AC，AD，BC和BD)，以及3次不超过n位的整数加法（分别对应于式（1）中的加号），此外还要做2次移位（分别对应于式（1）中乘2n和乘2n/2）。所有这些加法和移位共用O（n）步运算。设T（n）是2个n位整数相乘所需的运算总数，则由式（1），我们有：
（2）由此可得T（n）=O（n2）。因此，用（1）式来计算X和Y的乘积并不比小学生的方法更有效。要想改进算法的计算复杂性，必须减少乘法次数。为此我们把XY写成另一种形式：
XY=AC2n+[(A-B)(D-C)+AC+BD]2n/2+BD （3）
虽然，式（3）看起来比式（1）复杂些，但它仅需做3次n/2位整数的乘法（AC，BD和（A-B）（D-C）），6次加、减法和2次移位。由此可得：
（4）
用解递归方程的套用公式法马上可得其解为T(n)=O(nlog3)=O(n1.59)。利用式（3），并考虑到X和Y的符号对结果的影响，我们给出大整数相乘的完整算法MULT如下：
function MULT(X，Y，n); {X和Y为2个小于2n的整数，返回结果为X和Y的乘积XY}
begin
S=SIGN(X)*SIGN(Y); {S为X和Y的符号乘积}
X=ABS(X);
Y=ABS(Y); {X和Y分别取绝对值}
if n=1 then
if (X=1)and(Y=1) then return(S)
else return(0)
else begin
A=X的左边n/2位;
B=X的右边n/2位;
C=Y的左边n/2位;
D=Y的右边n/2位;
ml=MULT(A,C,n/2);
m2=MULT(A-B,D-C,n/2);
m3=MULT(B,D,n/2);
S=S*(m1*2n+(m1+m2+m3)*2n/2+m3);
return(S);
end;
end;
上述二进制大整数乘法同样可应用于十进制大整数的乘法以提高乘法的效率减少乘法次数。
【问题】 最接近点对问题
问题描述：
在应用中，常用诸如点、圆等简单的几何对象代表现实世界中的实体。在涉及这些几何对象的问题中，常需要了解其邻域中其他几何对象的信息。例如，在空中交通控制问题中，若将飞机作为空间中移动的一个点来看待，则具有最大碰撞危险的2架飞机，就是这个空间中最接近的一对点。这类问题是计算几何学中研究的基本问题之一。下面我们着重考虑平面上的最接近点对问题。
最接近点对问题的提法是：给定平面上n个点，找其中的一对点，使得在n个点的所有点对中，该点对的距离最小。
严格地说，最接近点对可能多于1对。为了简单起见，这里只限于找其中的一对。
这个问题很容易理解，似乎也不难解决。我们只要将每一点与其他n-1个点的距离算出，找出达到最小距离的两个点即可。然而，这样做效率太低，需要O(n2)的计算时间。我们能否找到问题的一个O (nlogn)算法。
这个问题显然满足分治法的第一个和第二个适用条件，我们考虑将所给的平面上n个点的集合S分成2个子集S1和S2，每个子集中约有n/2个点，然后在每个子集中递归地求其最接近的点对。在这里，一个关键的问题是如何实现分治法中的合并步骤，即由S1和S2的最接近点对，如何求得原集合S中的最接近点对，因为S1和S2的最接近点对未必就是S的最接近点对。如果组成S的最接近点对的2个点都在S1中或都在S2中，则问题很容易解决。但是，如果这2个点分别在S1和S2中，则对于S1中任一点p，S2中最多只有n/2个点与它构成最接近点对的候选者，仍需做n2/4次计算和比较才能确定S的最接近点对。因此，依此思路，合并步骤耗时为O(n2)。整个算法所需计算时间T(n)应满足：
T(n)=2T(n/2)+O(n2)
它的解为T(n)=O(n2)，即与合并步骤的耗时同阶，显示不出比用穷举的方法好。从解递归方程的套用公式法，我们看到问题出在合并步骤耗时太多。这启发我们把注意力放在合并步骤上。
为了使问题易于理解和分析，我们先来考虑一维的情形。此时S中的n个点退化为x轴上的n个实数x1、x2、…、xn。最接近点对即为这n个实数中相差最小的2个实数。我们显然可以先将x1、x2、…、xn排好序，然后，用一次线性扫描就可以找出最接近点对。这种方法主要计算时间花在排序上，因此如在排序算法中所证明的，耗时为O(nlogn)。然而这种方法无法直接推广到二维的情形。因此，对这种一维的简单情形，我们还是尝试用分治法来求解，并希望能推广到二维的情形。
假设我们用x轴上某个点m将S划分为2个子集S1和S2，使得S1={x∈S | x≤m}；S2={x∈S | x>m}。这样一来，对于所有p∈S1和q∈S2有p 递归地在S1和S2上找出其最接近点对{p1，p2}和{q1，q2}，并设δ=min{|p1-p2|，|q1-q2|}，S中的最接近点对或者是{p1，p2}，或者是{q1，q2}，或者是某个{p3，q3}，其中p3∈S1且q3∈S2。如图1所示。
图1 一维情形的分治法
我们注意到，如果S的最接近点对是{p3，q3}，即 | p3-q3 | < δ，则p3和q3两者与m的距离不超过δ，即 | p3-m | < δ，| q3-m | < δ，也就是说，p3∈(m-δ，m)，q3∈(m，m+δ)。由于在S1中，每个长度为δ的半闭区间至多包含一个点（否则必有两点距离小于δ），并且m是S1和S2的分割点，因此(m-δ，m)中至多包含S中的一个点。同理，(m，m+δ)中也至多包含S中的一个点。由图1可以看出，如果(m-δ，m)中有S中的点，则此点就是S1中最大点。同理，如果(m，m+δ)中有S中的点，则此点就是S2中最小点。因此，我们用线性时间就能找到区间(m-δ，m)和(m，m+δ)中所有点，即p3和q3。从而我们用线性时间就可以将S1的解和S2的解合并成为S的解。也就是说，按这种分治策略，合并步可在O(n)时间内完成。这样是否就可以得到一个有效的算法了呢？
还有一个问题需要认真考虑，即分割点m的选取，及S1和S2的划分。选取分割点m的一个基本要求是由此导出集合S的一个线性分割，即S=S1∪S2 ，S1∩S2=Φ，且S1 {x | x≤m}；S2 {x | x>m}。容易看出，如果选取m=[max（S）+min（S）]/2，可以满足线性分割的要求。选取分割点后，再用O(n)时间即可将S划分成S1={x∈S | x≤m}和S2={x∈S | x>m}。然而，这样选取分割点m，有可能造成划分出的子集S1和S2的不平衡。例如在最坏情况下，|S1|=1，|S2|=n-1，由此产生的分治法在最坏情况下所需的计算时间T（n）应满足递归方程：
T（n）=T（n-1）+O（n）
它的解是T（n）=O（n2）。这种效率降低的现象可以通过分治法中“平衡子问题”的方法加以解决。也就是说，我们可以通过适当选择分割点m，使S1和S2中有大致相等个数的点。自然地，我们会想到用S的n个点的坐标的中位数来作分割点。在选择算法中介绍的选取中位数的线性时间算法使我们可以在O（n）时间内确定一个平衡的分割点m。
至此，我们可以设计出一个求一维点集S中最接近点对的距离的算法pair如下。
Float pair（S）;
{ if | S | =2 δ= | x[2]－x[1] | /*x[1..n]存放的是S中n个点的坐标*/
else
{ if ( | S | =1) δ=∞
else
{ m=S中各点的坐标值的中位数;
构造S1和S2，使S1={x∈S | x≤m}，S2={x∈S | x＞m};
δ1=pair(S1);
δ2=pair(S2);
p=max(S1);
q=min(S2);
δ=min(δ1，δ2，q-p);
}
return(δ);
}
由以上的分析可知，该算法的分割步骤和合并步骤总共耗时O(n)。因此，算法耗费的计算时间T(n)满足递归方程：
解此递归方程可得T(n)=O(nlogn)。
【问题】循环赛日程表
问题描述：设有n=2k个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表：
（1）每个选手必须与其他n-1个选手各赛一次；
（2）每个选手一天只能参赛一次；
（3）循环赛在n-1天内结束。
请按此要求将比赛日程表设计成有n行和n-1列的一个表。在表中的第i行，第j列处填入第i个选手在第j天所遇到的选手。其中1≤i≤n，1≤j≤n-1。
按分治策略，我们可以将所有的选手分为两半，则n个选手的比赛日程表可以通过n/2个选手的比赛日程表来决定。递归地用这种一分为二的策略对选手进行划分，直到只剩下两个选手时，比赛日程表的制定就变得很简单。这时只要让这两个选手进行比赛就可以了。
1 2 3 4 5 6 7
1 2 3 4 5 6 7 8
2 1 4 3 6 7 8 5
3 4 1 2 7 8 5 6
1 2 3 4 3 2 1 8 5 6 7
1 2 3 4 5 6 7 8 1 4 3 2
1 2 1 4 3 6 5 8 7 2 1 4 3
1 2 3 4 1 2 7 8 5 6 3 2 1 4
2 1 4 3 2 1 8 7 6 5 4 3 2 1
（1） （2） （3）
图1 2个、4个和8个选手的比赛日程表
图1所列出的正方形表（3）是8个选手的比赛日程表。其中左上角与左下角的两小块分别为选手1至选手4和选手5至选手8前3天的比赛日程。据此，将左上角小块中的所有数字按其相对位置抄到右下角，又将左下角小块中的所有数字按其相对位置抄到右上角，这样我们就分别安排好了选手1至选手4和选手5至选手8在后4天的比赛日程。依此思想容易将这个比赛日程表推广到具有任意多个选手的情形。
八、动态规划法
经常会遇到复杂问题不能简单地分解成几个子问题，而会分解出一系列的子问题。简单地采用把大问题分解成子问题，并综合子问题的解导出大问题的解的方法，问题求解耗时会按问题规模呈幂级数增加。
为了节约重复求相同子问题的时间，引入一个数组，不管它们是否对最终解有用，把所有子问题的解存于该数组中，这就是动态规划法所采用的基本方法。以下先用实例说明动态规划方法的使用。
【问题】 求两字符序列的最长公共字符子序列
问题描述：字符序列的子序列是指从给定字符序列中随意地（不一定连续）去掉若干个字符（可能一个也不去掉）后所形成的字符序列。令给定的字符序列X=“x0，x1，…，xm-1”，序列Y=“y0，y1，…，yk-1”是X的子序列，存在X的一个严格递增下标序列，使得对所有的j=0，1，…，k-1，有xij=yj。例如，X=“ABCBDAB”，Y=“BCDB”是X的一个子序列。
给定两个序列A和B，称序列Z是A和B的公共子序列，是指Z同是A和B的子序列。问题要求已知两序列A和B的最长公共子序列。
如采用列举A的所有子序列，并一一检查其是否又是B的子序列，并随时记录所发现的子序列，最终求出最长公共子序列。这种方法因耗时太多而不可取。
考虑最长公共子序列问题如何分解成子问题，设A=“a0，a1，…，am-1”，B=“b0，b1，…，bm-1”，并Z=“z0，z1，…，zk-1”为它们的最长公共子序列。不难证明有以下性质：
（1） 如果am-1=bn-1，则zk-1=am-1=bn-1，且“z0，z1，…，zk-2”是“a0，a1，…，am-2”和“b0，b1，…，bn-2”的一个最长公共子序列；
（2） 如果am-1!=bn-1，则若zk-1!=am-1，蕴涵“z0，z1，…，zk-1”是“a0，a1，…，am-2”和“b0，b1，…，bn-1”的一个最长公共子序列；
（3） 如果am-1!=bn-1，则若zk-1!=bn-1，蕴涵“z0，z1，…，zk-1”是“a0，a1，…，am-1”和“b0，b1，…，bn-2”的一个最长公共子序列。
这样，在找A和B的公共子序列时，如有am-1=bn-1，则进一步解决一个子问题，找“a0，a1，…，am-2”和“b0，b1，…，bm-2”的一个最长公共子序列；如果am-1!=bn-1，则要解决两个子问题，找出“a0，a1，…，am-2”和“b0，b1，…，bn-1”的一个最长公共子序列和找出“a0，a1，…，am-1”和“b0，b1，…，bn-2”的一个最长公共子序列，再取两者中较长者作为A和B的最长公共子序列。
定义c[i][j]为序列“a0，a1，…，ai-2”和“b0，b1，…，bj-1”的最长公共子序列的长度，计算c[i][j]可递归地表述如下：
（1）c[i][j]=0 如果i=0或j=0；
（2）c[i][j]= c[i-1][j-1]+1 如果I，j>0，且a[i-1]=b[j-1]；
（3）c[i][j]=max（c[i][j-1]，c[i-1][j]） 如果I，j>0，且a[i-1]!=b[j-1]。
按此算式可写出计算两个序列的最长公共子序列的长度函数。由于c[i][j]的产生仅依赖于c[i-1][j-1]、c[i-1][j]和c[i][j-1]，故可以从c[m][n]开始，跟踪c[i][j]的产生过程，逆向构造出最长公共子序列。细节见程序。
# include
# include
# define N 100
char a[N],b[N],str[N];
int lcs_len(char *a, char *b, int c[ ][ N])
{ int m=strlen(a), n=strlen(b), i,j;
for (i=0;i<=m;i++) c[i][0]=0;
for (i=0;i<=n;i++) c[0][i]=0;
for (i=1;i<=m;i++)
for (j=1;j<=m;j++)
if (a[i-1]==b[j-1])
c[i][j]=c[i-1][j-1]+1;
else if (c[i-1][j]>=c[i][j-1])
c[i][j]=c[i-1][j];
else
c[i][j]=c[i][j-1];
return c[m][n];
}
char *buile_lcs(char s[ ],char *a, char *b)
{ int k, i=strlen(a), j=strlen(b);
k=lcs_len(a,b,c);
s[k]=’\0’;
while (k>0)
if (c[i][j]==c[i-1][j]) i--;
else if (c[i][j]==c[i][j-1]) j--;
else { s[--k]=a[i-1];
i--; j--;
}
return s;
}
void main()
{ printf (“Enter two string
