原创 Divide and conquer method

 2013-11-8 19:18  589 9 1

void div(p,q) {
int n，A[n]； //定义成全程变量
int m，p，q； //1≤p≤q≤n
if(small(p,q)) return(answer(p,q))；
else
{
m = divide(p,q)； //p≤m＜q
return (combine(div(p,m)，div(m＋1,q)))；
}；
}//div

　　在这个算法中，small(p,q)是一个布尔值函数，它用以判断输入为A(p:q)的问题是否小到无需进一步细分就能算出其答案的程度。若是，则调用能直接计算此规模下的子问题解的函数answer(p,q)；若否，则调用分割函数divide(p,q)，返回一个新的分割点m(整数)。于是，原问题被分成输入为A(p:m)和A(m+1:q)的两个子问题。对这两个子问题分别递归调用div得到各自的解x和y，再用一个合并函数combine(x,y)将这两个子问题的解合成原问题(输入为 A(p,q))的解。倘若所分成的两个子问题的输入规模大致相等，则div总的计算时间可用下面的递归关系式来表示：
g(n) 当n足够小，　　　　　　　　　　　　　　　　　

T(n)＝　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

　　　　2T(n/2)+f(n) 否则
其中，T(n)是输入规模为n的div的运行时间，g(n)是输入规模足够小以至于能直接求解时的运行时间，f(n)是combine的时间

显然用递归过程描述以分治法为基础的算法是理所当然的，但为了提高效率，往往需要将这一递归形式转换成迭代形式。例如下面这个算法：

void div1（p,q) {
//div的迭代模型，定义了一个适当大小的工作栈
int s，t；
intiStack(sqStack)； //定义工作栈sqStack
L1：while(!small(p,q)) {
m = divied(p,q)； //确定如何分割输入
push(sqStack,(p,q,m,0,2))； //处理第一次递归调用
q = m；
}；//while
t = answer(p,q)；
while(!StackEmpty( sqStack )) {
pop(sqStack,(p, q, m, s, ret))； //退栈，ret为返回地址
if(ret==2) {
push(sqStack,(p, q, m, t, 3))； //处理第二次递归调用
p = m + 1；
go to L1；}
else {
t = combine(s,t)； //将两个子问题的解合并成一个解
}；//if
}；//while
return t；
}//div1 　　当然，这个算法还可以简化