C++分治法求最值.doc

实验内容：用分治法求最大最小值题目来源： 教材 页 题 教师补充 自选题目主要功能描述：(1) 对一组数进行比较大小，求出其中的最大值和最小值，利用分治法的原理来实现。(2) 先对数组中元素个数进行判断，只有一个元素时，最大值max和最小值min都是它本身；当有两个元素时，比较两个数的大小，大者为最大值max，小者为最小值min；当数组中元素多于两个时，里用分治法原理，递归调用MaxMin函数，求出划分出的每组中的最值与另外一组最值比较，最后的得出最大值max和最小值min。设计分析：分析数组中的元素：有一个元素、两个元素、两个以上元素（1） 最大值最小值都是同一个元素，不用判断直接赋值min、max（2） 两个元素时：判断两个元素的大小，大数为最大值max，小数为最小值min（3） 两个以上元素是：使用函数void SortableList:MaxMin(int i,int j,T &max,T &min)const ；里用分治法的原理，把问题变成可以用两个元素或者一个元素求出最值，然后比较每次求出的两个最值的大小，大数为max，小数为min，直到最后求出最大值max和最小值min。典型测试数据测试：520 30 40 456 12 812 8 20 60 50 123 87 100125220 30输出：程序及运行结果正误判断： 非常好 正确，还可改进 基本正确，还需改进 还有错误 不足之处或设计经验小结： 任课教师评语：教师签字： 年月日程序设计课程上机实验报告注：每学期至少有一次设计性实验。每学期结束请任课教师按时按量统一交到教学秘书处。源程序文件名及组成文件：重要变量用途说明 算法描述#include /导入头文件using namespace std;template /template函数模板 class SortableList private: T *array; /定义数组，用来存储求最值的数组int maxSize; /定义数组长度public: SortableList();void SetMaxSize() coutmaxSize; /输入数组长度array=new TmaxSize; /定义存储空间 int GetMaxSize() /返回数组长度 return maxSize; void InputArray() /输入数组中元素int i;for(i=0;imaxSize;i+)cout请输入(i+1)arrayi;void dispayArray() /输出数组中元素int i;cout输出数组中元素为：;for(i=0;imaxSize;i+)coutarrayi ;coutendl;void MaxMin(int i,int j,T &max,T &min)const; /最值函数声明SortableList()delete array; /定义析构函数，释放空间; template void SortableList:MaxMin(int i,int j,T &max,T &min)const /定义求最大值，最小值函数 T min1,max1; if(i=j) max=min=arrayi; else if(i=j-1) if(arrayiarrayj) max=arrayj;min=arrayi; else max=arrayi;min=arrayj; else int m=(i+j)/2; MaxMin(i,m,max,min); /求前半部子表中的最大、最小元 MaxMin(m+1,j,max1,min1); /求后半部子表中的最大、最小元 if(maxmin1)min=min1; /两表中最小元的小者为原表最小元 int main() int Max,Min; /存储数组中的最大，最小值int size;SortableList a; a.SetMaxSize();size=a.GetMaxSize()-1; /取得数组元素中最大下标值a.InputArray();a.di