文档介绍：第二章分治法( Divide and Conquer) ——“分”而治之 一般方法?对大规模问题的求解?利用分治法求解大规模问题 ,将整个问题分成若干个小问题,然后分而治之。可用递归过程描述。一般情况下,子问题与原始问题“同质”算法 分治策略的抽象化控制 procedure DANDC(p,q ) global (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 // BINE(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( ):当规模 q-p+1 还较大时,对规模为 q-p+1 的子问题进一步分解,返回值为[ p,q ]区间进一步的分割点; ? COMBINE(x,y ):子结果的合并函数,将区间[ p,m ]和[m+1,q] 上的子问题的解合并成区间[ p,q ]上的“较完整”的解。当 p=1,q=n 时,就得到整个问题的解。 2. 分治策略的抽象化控制过程? DANDC 的计算时间若所分成的两个子问题的规模大致相等,则 DANDC 总的计算时间可用递归关系式表示如下: g(n ) n 足够小 T(n ) = 2T(n/2) + f(n ) 否则注: ? T(n ):表示输入规模为 n的 DANDC 计算时间? g(n ):表示对足够小的输入规模直接求解的计算时间? f(n ):BINE 对两个子区间的子结果进行合并的时间(该公式针对具体问题有各种不同的变形) 二分检索(折半查找) 1. 问题的描述已知一个按非降次序排列的元素表 a 1 , a 2 , …,a n,判定某给定的元素 x是否在该表中出现。?若是,则找出 x在表中的位置并返回其所在位置的下标?若非,则返回 0值。问题的形式描述: I=(n, a 1 , a 2 , …,a n ,x) ?问题分解:选取下标 k,由此将 I分解为 3个子问题: I 1 =(k-1, a 1 , a 2 , …,a k-1 ,x) I 2 =(1, a k ,x) I 3 =( n-k , a k+1 , a 2 , …,a n ,x) ?对于 I 2,若 a k =x ,则有解 k,对 I 1、I 3不用再求解;否则, ?若x< a k,则只在 I 1中求解,对 I 3不用求解; ?若x> a k,则只在 I 3中求解,对 I 1不用求解; ?对I 1、I 3的求解可再次采用分治方法求解——递归求解过程 2. 二分检索二分检索:每次选取中间元素的下标算法 二分检索 procedure BINSRCH(A,n,x,j ) integer low,high,mid,j,n ; low ← 1; high ← n; while low ≤ high do mid ← case :x<A(mid):high ← mid-1 :x> A(mid):low ← mid+1 : else:j ← mid;return endcase repeat j ←0 end BINSRCH ?? high)/2 (low ?注:给定一个按非降次序排列的元素数组 A(1:n) ,n≥1, 判断 x是否出现。?若是,置 j,使得 x=A(j ) ?若非, j=0 例 :设 A(1:9)=(-15 , -6,0,7,9, 23 , 54 , 82 , 101) 在A中检索 x=101 , -14 , 82 。执行轨迹见下表 1 找到找到找不到 12999 898111898 796241796 591591591 mid high low mid high low mid high