资源描述：
《计算机算法基础第二章ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第二章分治法——“分”而治之2.1一般方法对大规模问题的求解利用分治法求解大规模问题1.基本思想分而治之方法与软件设计的模块化方法非常相似。为解决一个大问题，可以（1）把它分解成两个或多个更小的问题；（2）分别解决每个小问题；（3）把各小问题的解答组合起来，即可得到原问题的解。小问题通常与原问题相似或同质，因而可以递归地使用分而治之策略解决。8/5/2021通常，子问题与原始问题“同质”8/5/2021例[找伪币]假设16枚金币中有一枚是伪造的，真假金币的区别仅是重量不同(伪币轻一些），利用一个没有砝码的天平作
2、工具，找出这枚伪造的金币。方法1：比较硬币1和2的重量，有一个轻则找到；否则比较硬币3和4，依次比较下去，直到找到。最多8次比较。方法2：利用分治法。16个硬币分为两组，每组8个，比较重量，伪币在轻的一组。将轻的一组再分为两组，每组4个……继续划分下去，依次每组2个，每组1个，此时找到。8/5/2021算法2.1分治策略的抽象化控制procedureDANDC(p,q)globaln.A(1:n);integerm,p,q;//1≤p≤q≤n//ifSMALL(p,q)thenreturn(G(p,q))els
3、em←DIVIDE(p,q)//p≤m＜q//return(COMBINE(DANDC(p,m),DANDC(m+1,q)))endifendDANDC注：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
4、)：子结果的合并函数，将区间[p,m]和[m+1,q]上的子问题的解合并成上级区间[p,q]上的“较完整”的解。当p=1,q=n时，就得到整个问题的解。2.分治策略的抽象化控制8/5/2021DANDC的计算时间若所分成的两个子问题的输入规模大致相等，则DANDC总的计算时间可用递归关系式表示，如下：g(n)n足够小T(n)=2T(n/2)+f(n)否则注：T(n)：表示输入规模为n的DANDC计算时间g(n)：表示对足够小的输入规模直接求解的计算时间f(n)：表示COMBINE对两个子区间的子结果进行合并的时
5、间（该公式针对具体问题有各种不同的变形）8/5/20212.2二分检索（折半查找）1.问题的描述已知一个按非降次序排列的元素表a1,a2,…,an,判定某给定的元素x是否在该表中出现。若是，则找出x在表中的位置并返回其所在下标若非，则返回0值。8/5/2021分治求解策略分析：定义问题的形式描述：I=(n,a1,a2,…,an,x)问题分解：选取下标k，由此将I分解为3个子问题：I1=(k-1,a1,a2,…,ak-1,x)I2=(1,ak,x)I3=(n-k,ak+1,a2,…,an,x)对于I2，若ak=x
6、，则有解k，对I1、I3不用再求解；否则，若xak，则只在I3中求解，对I1不用求解；I1、I3上的求解可再次采用分治方法划分后求解（递归过程）8/5/20212.二分检索算法算法2.3二分检索procedureBINSRCH(A,n,x,j)integerlow,high,mid,j,n;low←1;high←n;whilelow≤highdomid←case:xA(mid):low←mid+1:else:j←mid;r
7、eturnendcaserepeatendBINSRCH注：给定一个按非降次序排列的元素数组A(1:n)，n≥1,判断x是否出现。若是，置j，使得x=A(j)若非，j=08/5/2021例2.1：设A(1:9)=(-15，-6，0，7，9，23，54，82，101)在A中检索x=101，-14，82。执行轨迹见下表1表1运行轨迹示例x=101x=-14x=82lowhighmidlowhighmidlowhighmid19519519569714269789811189899921找不到找到找到成功的检索不成功
8、的检索成功的检索8/5/20213.算法的正确性证明定理2.1过程BINSRCH(A,n,x,j)能正确运行证明：1）在具体指定A中的数据元素及x的数据类型后，算法中的所有运算都能按要求正确运行——即首先满足确定性和能行性2）终止性算法初始部分置low←1,high←n①若n=0，不进入循环，j置0，算法终止②否则，进入循环，计算mid,或x=A(mid)，j置为mid，算法终止；或x
