您好,欢迎访问三七文档
实验一分治法一、实验目的1.理解分治法的方法;2.掌握使用分治法解决一般问题的步骤;3.掌握分治算法求解数组的最大值和最小值的方法。二、实验原理在一个给定数组中查找最大值和最小值是一类常见的问题,也是解决其他一些算法的基础。假设给定数组为a,数组中含有n个元素,一般的算法是在数组中进行直接查找,算法伪代码如下:1.x←a[0];y←a[0]2.fori←2ton3.ifa[i]xthenx←a[i]4.ifa[i]ytheny←a[i]5.endfor6.return(x,y)上述代码在第3行和第4行涉及到元素的比较,每次循环进行2次比较,而循环的次数在算法第2行给出,为(n-2)+1=n-1次,因此,算法元素比较总次数为2(n-1)次。现在采用分治的思想,假设数组的长度为2的整数幂,将数组分割成两半,分别为a[0…(n/2)-1]和a[n/2…n-1],在每一半中分别查找最大值和最小值,并返回这两个最小值中的最小值以及两个最大值中的最大值。假设给定数组为a,数组的下标上界和下界分别为low和high,则其算法伪代码如下:minmax(a,low,high)1.ifhigh-low=1then2.ifa[low]a[high]thenreturn(a[low],a[high])3.elsereturn(a[high],a[low])4.endif5.else6.mid←|_(low+high)/2_|7.(x1,y1)←minmax(a,low,mid)8.(x2,y2)←minmax(a,mid+1,high)9.x←min{x1,x2}10.y←max{y1,y2}11.return(x,y)12.endif代码第1行high-low=1表示数组长度为1,此时执行第2行~第4行代码直接比较数组的两个元素,选出最大值和最小值,此为函数的递归终止条件;代码第7行和第8行是两个递归调用,分别在数组的下标范围[low,mid]和[mid+1,high]查找最小值和最大值,第9行比较两个最大值取其中较大者,第10行比较两个最小值取较大者。代码的第2、9和10行涉及到元素的比较,第7、8行由于递归也产生元素比较,因此令算法总的元素比较次数为C(n),则有22)2/(221)(nnCnnC若若对递推式进行求解22/322)2/(2)2(222...22)2/(2...248)8/(824)2)8/(2(424)4/(42)2)4/(2(22)2/(2)(11122111nnCnCnCnCnCnCnCnCkkjjkkkkk得到minmax算法的元素比较总次数为3n/2-2,优于直接比较的性能。三、实验内容及要求1.编写程序使用分治算法MINMAX求解数组的最小值和最大值,并用实际数组对算法进行测试。2.要求算法中元素比较的次数为3n/2-2,在程序中元素比较的地方进行记录,并在程序末尾输出数组最大值和最小值以及元素比较次数。四、实验步骤1.定义结构体类型或类,用以在函数的返回值同时返回数组的最大值和最小值。结构体定义可以参考:structT{intmax,min;};类的定义可以参考:classT{private:intmax,min;public:intgetMax(){…}intgetMin(){…}voidsetMax(intmax){…}voidsetMin(intmin){…}}2.编写函数MINMAX求解数组最大值和最小值,函数头为:TMINMAX(inta[],intlow,inthigh)a为数组名,low和high分别为数组的下标上界和下界。3.在main函数中使用给定数组{21,25,49,16,25,6,78,1}测试MINMAX函数并输出元素比较次数,效果如下图所示。五、思考和作业1.试修改程序MINMAX,使得当数组长度n不是2的整数幂也能运行,并分析修改后算法的元素比较次数。2.使用分治算法解决最大子数组和问题,问题描述如下:给定一个整数序列S,找出S中的连续子序列,使得该子序列和最大,要求算法时间复杂性为Θ(nlogn)。例如:-2,11,-4,13,-5,-2;结果为20:(11,-4,13)。提示:假定要寻找子数组S[low…high]的最大子数组,使用分治法将数组分解成两个尽可能想相等的子数组,找到子数组中点mid,则S[low…high]中任何连续数组S[i…j]必然是一下三种情况之一:完全位于S[low…mid]中,low≤i≤j≤mid完全位于S[mid+1…high]中,midi≤j≤high跨越中点mid,low≤i≤midj≤high因此,S[low…high]的一个最大子数组所处的位置必然是三种情况之一。可以通过递归方法求解A[low…mid]和A[mid+1…high]的最大子数组,则剩下的问题就是求解跨越中点的最大子数组,然后在三种情况下选择最大者。Part1Part2thesubwithlargestsummaybein:Part1Part2or:Part1Part2recursionThelargestistheresult
本文标题:-实验1分治法
链接地址:https://www.777doc.com/doc-6060268 .html