-实验1分治法(总3页)

1、实验一 分治法一、实验目的1理解分治法的方法；2. 掌握使用分治法解决一般问题的步骤；3. 掌握分治算法求解数组的最大值和最小值的方法。二、实验原理在一个给定数组中查找最大值和最小值是一类常见的问题，也是解决其他一些算法的基础。假设给定数组为a，数组中含有n个元素，一般的算法是在数组中进行直接查找，算法伪代码如下：1. xa0; ya02. for i2 to n3. if aiy then yai5. end for6. return (x,y)上述代码在第3行和第4行涉及到元素的比较，每次循环进行2次比较，而循环的次数在算法第2行给出，为(n-2)+1=n-1次，因此，算法元素比较总次数为

2、2(n-1)次。现在采用分治的思想，假设数组的长度为2的整数幂，将数组分割成两半，分别为a0(n/2)-1和an/2n-1，在每一半中分别查找最大值和最小值，并返回这两个最小值中的最小值以及两个最大值中的最大值。假设给定数组为a，数组的下标上界和下界分别为low和high，则其算法伪代码如下：minmax(a,low,high)1. if high-low=1 then2. if alowahigh then return (alow,ahigh)3. else return (ahigh,alow)4. end if5. else6. mid|_(low+high)/2_|7. (x1,y1

3、)minmax(a,low,mid)8. (x2,y2)minmax(a,mid+1,high)9. xminx1,x210. ymaxy1,y211. return (x,y)12.end if代码第1行high-low=1表示数组长度为1，此时执行第2行第4行代码直接比较数组的两个元素，选出最大值和最小值，此为函数的递归终止条件；代码第7行和第8行是两个递归调用，分别在数组的下标范围low,mid和mid+1,high查找最小值和最大值，第9行比较两个最大值取其中较大者，第10行比较两个最小值取较大者。代码的第2、9和10行涉及到元素的比较，第7、8行由于递归也产生元素比较，因此令算法总的

4、元素比较次数为C(n)，则有对递推式进行求解得到minmax算法的元素比较总次数为3n/2-2，优于直接比较的性能。三、实验内容及要求1. 编写程序使用分治算法MINMAX求解数组的最小值和最大值，并用实际数组对算法进行测试。2. 要求算法中元素比较的次数为3n/2-2，在程序中元素比较的地方进行记录，并在程序末尾输出数组最大值和最小值以及元素比较次数。四、实验步骤1. 定义结构体类型或类，用以在函数的返回值同时返回数组的最大值和最小值。 结构体定义可以参考：struct T int max,min;类的定义可以参考：class T private: int max,min; public:

5、int getMax() int getMin() void setMax(int max) void setMin(int min) 2. 编写函数MINMAX求解数组最大值和最小值，函数头为：T MINMAX(int a,int low,int high)a为数组名，low和high分别为数组的下标上界和下界。3. 在main函数中使用给定数组21,25,49,16,25,6,78,1测试MINMAX函数并输出元素比较次数，效果如下图所示。五、思考和作业1. 试修改程序MINMAX，使得当数组长度n不是2的整数幂也能运行，并分析修改后算法的元素比较次数。2. 使用分治算法解决最大子数组和问

6、题，问题描述如下：给定一个整数序列S，找出S中的连续子序列，使得该子序列和最大，要求算法时间复杂性为(nlogn)。例如：-2, 11, -4, 13, -5, -2; 结果为20: (11, -4, 13)。提示：假定要寻找子数组Slowhigh的最大子数组，使用分治法将数组分解成两个尽可能想相等的子数组，找到子数组中点mid，则Slowhigh中任何连续数组Sij必然是一下三种情况之一：l 完全位于Slowmid中，lowijmidl 完全位于Smid+1high中，midijhighl 跨越中点mid，lowimidjhigh因此，Slowhigh的一个最大子数组所处的位置必然是三种情况之一。可以通过递归方法求解Alowmid和Amid+1high的最大子数组，则剩下的问题就是求解跨越中点的最大子数组，然后在三种情况下选择最大者。Part 1Part