2.分治策略的抽象化控制 算法31分治策略的抽象化控制注: procedure DANDC(p, q k=2:二分是最常用的分解策略; global, A(1: n) > SMALL(P,q):布尔函数,判断输入 integer m,p,q;∥1≤p≤q≤n∥ 规模q-p+1是否足够小而无需再进 if SMall(p, q) 步分就可求解; then return(G(p, >G(p,q):对输入规模为qp+1的子问 else 题求解( SMALL(pq为真时); m←DVDE(p,q)∥≤m<q >DVDE(pq):对输入规模为q-p+ 的子问题进一步分解,返回值为[pq] return( COMBINE(DANDC(Pm,区间进一步的分割点( SMALL(p,q DANDO(m+1,q)为假时 endif COMBINE(xy):子结果的合并函数, end dand 将区间[p,m和[m+1,q上的子问题 的解合并成上级区间[p,q]上的“较 完整”的解。当p=1,qn时,就得到 整个问题的解。算法3.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)：对输入规模为q-p+1的子问 题求解（SMALL(p,q)为真时）； ➢ DIVIDE(p.q)：对输入规模为q-p+1 的子问题进一步分解，返回值为[p,q] 区间进一步的分割点（SMALL(p,q) 为假时； ➢ COMBINE(x,y)：子结果的合并函数， 将区间[p,m]和[m+1,q]上的子问题 的解合并成上级区间[p,q]上的“较 完整”的解。当p=1,q=n时，就得到 整个问题的解。 2. 分治策略的抽象化控制