计算机算法基础(第二章).ppt

2017-2-23计算机算法基础 2017-2-23 第二章分治法——“分”而治之 一般方法?对大规模问题的求解?利用分治法求解大规模问题 ,无法直接求解,则采用将整个问题分成若干个小问题后分而治之。一般情况下,子问题与原始问题“同质” 2017-2-23 算法 分治策略的抽象化控制 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) :对输入规模为 q-p+1 的子问题求解( SMALL(p,q) 为真时); ? DIVIDE() :对输入规模为 q- p+1 的子问题进一步分解,返回值为[p,q] 区间进一步的分割点( SMALL(p,q) 为真时; ? COMBINE(x,y) :子结果的合并函数,将区间[p,m] 和[m+1,q] 上的子问题的解合并成上级区间[p,q] 上的“较完整”的解。当 p=1,q=n 时, 就得到整个问题的解。 2. 分治策略的抽象化控制 2017-2-23 ? DANDC 的计算时间若所分成的两个子问题的输入规模大致相等,则 DANDC 总的计算时间可用递归关系式表示,如下: g(n) n 足够小 T(n) = 2T(n/2) + f(n) 否则注: ? T(n) :表示输入规模为 n的 DANDC 计算时间? g(n) :表示对足够小的输入规模直接求解的计算时间? f(n) :BINE 对两个子区间的子结果进行合并的时间(该公式针对具体问题有各种不同的变形) 2017-2-23 二分检索(折半查找) 1. 问题的描述已知一个按非降次序排列的元素表 a 1 , a 2 , …,a n,判定某给定的元素 x是否在该表中出现。?若是,则找出 x在表中的位置并返回其所在下标?若非,则返回 0值。 2017-2-23 分治求解策略分析: ?定义问题的形式描述: 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 , ak +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上的求解可再次采用分治方法划分后求解( 递归过程) 2017-2-23 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 end NIBSRCH ?? high)/2 (low ?注:给定一个按非降次序排列的元素数组 A(1:n) , n≥1,判断 x是否出现。?若是,置 j,使得 x=A(j) ?若非, j=0 2017-2-23 例 :设 A(1:9)=(-15 , -6,0,7,9, 23 , 54 , 82 , 101) 在A中检索 x=101 , -14 , 82 。执行轨迹见下表 1 表1 运行轨迹示例 x=101 x=-14