ACM程序设计分治与递归ppt课件.ppt

《ACM程序设计分治与递归ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五讲分治与递归引言分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。战术算法设计技术划分——治理——组合将要求解的较大规模的问题分割成k个更小规模的子问题。算法总体思想nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n

2、/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)直到问题规模足够小，很容易求出其解为止。可将规模为n的问题分解为多少个规模为n/2的子问题？为什么不一定是两个？将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)问题一：在一个整数组A[1.

3、..n]中，同时寻找最大值和最小值例一一个简单例子方法一：顺序扫描法S1:min=A[1];max=A[1];S2:扫描数组，对i从2到n做：S2a:如果A[i]max，则max=A[i];S3:返回x,y的值比较次数：2n-2方法二：分治法基本思想：（1）划分：将数组分割成两半（2）治理：在每一半中找到最大值和最小值。（3）合并：返回两个最大值中的最大值和两个最小值中的最小值。算法1Minmax(intlow,inthigh){ifhigh-low=1then//如果只有两个元素直接解决i

4、fA[low]

5、两个值，显然是不符合C语言语法的，请给出你的解决方案（2）C中函数参数的传递是传值传递Minmax(intA[],intlow,inthigh,int*x,int*y){if(high-low==1)if(A[low]

6、时间复杂度分析：1若n=2C(n)=2C(n/2)+2若n>2求解递推式得：C(n)=3n/2-2例二二分搜索问题：在一个有序序列中搜索给定值x，若找到，返回x所在位置，否则返回查找失败标志-1。二分搜索过程145789101215222327323512152223273235midmid121522查找成功！22因A[mid]<22，丢弃A[mid]及其左边所有元素midmid算法2.1二分搜索的非递归算法intBinarySearch(inta[],intn,intx){intlow=0;high=n-1;while(high>=low

7、){//待搜区间非空intmid=(low+high)/2;if(x==a[mid])returnmid;//查找成功if(xhigh)return-1//待搜区间为空else{intmid=(low+high)/2;if(x==a[mid])returnmid;//查找成功if(x

8、arch(a,x,low,mid-1);elsereturnBSearch(a,x,mid+1,high);}}二分搜索算法分析时间复杂度分析：1若n=1C(n)=