分治法第k小元素poj

《分治法第k小元素poj》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第六章分治6.1引言分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。战略算法设计技术划分——治理——组合将要求解的较大规模的问题分割成k个更小规模的子问题。6.1.1算法总体思想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/4)T(

2、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)棋盘覆盖问题n=8问题一：在一个整数组A[1...n]中，

3、同时寻找最大值和最小值6.1.2一个简单例子方法一：顺序扫描法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）合并：返回两个最大值中的最大值和两个最小值中的最小值。算法6.1Minmax(intlow,inthigh){ifhigh-low=1thenifA[low]

4、(A[low],A[high])elsereturn(A[high],A[low])endifelsemid=(low+high)/2(x1,y1)=minmax(low,mid)(x2,y2)=minmax(mid+1,high)x=min{x1,x2};y=max(y1,y2)return(x,y)endif讨论（1）请将以上算法改写为C程序注意：（1）以上算法要求函数同时返回两个值，显然是不符合C语言语法的，请给出你的解决方案（2）C中函数参数的传递是传值传递Minmax(intA[],intlow,inthigh,int*x,int*y){if(high

5、-low==1)if(A[low]2求解递推式得：C(n)=3n/2-26.2二分搜索问题：在一个有序序列中搜索给定值x，若找到，返回x所在位置，否则返回查找失败标志-1。二分搜

6、索过程145789101215222327323512152223273235midmid121522查找成功！22因A[mid]<22，丢弃A[mid]及其左边所有元素midmid算法6.2二分搜索的非递归算法intBinarySearch(inta[],intn,intx){intlow=0;high=n-1;while(high>=low){//待搜区间非空intmid=(low+high)/2;if(x==a[mid])returnmid;//查找成功if(x

7、败，返回-1}算法6.3二分搜索的递归算法intBSearch(inta[],intn,intx,intlow,inthigh){if(low>high)return-1//待搜区间为空else{intmid=(low+high)/2;if(x==a[mid])returnmid;//查找成功if(x

8、1...n]排序用分治策