2.分治策略的抽象化控制过 算法21分治策略的抽象化控制注 procedure DANDC(p, g) k=2:二分是最常用的分解策略; global nA(1: n > SMALL(p,q):布尔函数,判断输 integer m,p,q;∥1p≤q≤n 入规模q-p+1是否足够小而无需再 进一步分航就可求解; if SMALL(p, g) >G(p,q):当 SMALL(pq)为真时, then return(G(p, g)) 对输入规模为q-p+1的子问题求解 else DVDE(pq):当规模q-p+1还较 m← DIVIDE(p,q)/lp≤m<q∥ 大时,对规模为q-p+1的子问题进 retun (COMBINE(DANDC(p, m), 步分解,返回值为[pq]区间进 DANDC(m+1, g)) 步的分割点; endif COMBIN(xy):子结果的合并函 end dand 数,将区间pm和[m+1q]上的子 问题的解合并成区间[q]上的 “较完整”的解。当p=1,q=n时, 就得到整个问题的解算法2.1 分治策略的抽象化控制 procedure DANDC(p,q) global n.A(1:n); integer m,p,q; //1≤p≤q≤n// if SMALL(p,q) then return(G(p,q)) else m←DIVIDE(p,q) //p≤m＜q// return(COMBINE(DANDC(p,m), DANDC(m+1,q))) endif end DANDC 注： ➢ k=2: 二分是最常用的分解策略； ➢ SMALL(p,q)：布尔函数，判断输 入规模q-p+1是否足够小而无需再 进一步分就可求解； ➢ G(p,q)： 当SMALL(p,q)为真时， 对输入规模为q-p+1的子问题求解； ➢ DIVIDE(p.q)：当规模q-p+1还较 大时，对规模为q-p+1的子问题进 一步分解，返回值为[p,q]区间进 一步的分割点； ➢ COMBINE(x,y)：子结果的合并函 数，将区间[p,m]和[m+1,q]上的子 问题的解合并成区间[p,q]上的 “较完整”的解。当p=1,q=n时， 就得到整个问题的解。 2. 分治策略的抽象化控制过程