《C++分治法求最值》由会员分享,可在线阅读,更多相关《C++分治法求最值(5页珍藏版)》请在金锄头文库上搜索。
1、实验内容:用分治法求最大最小值题目来源: 教材 页 题 教师补充 自选题目主要功能描述:(1) 对一组数进行比较大小,求出其中的最大值和最小值,利用分治法的原理来实现。(2) 先对数组中元素个数进行判断,只有一个元素时,最大值max和最小值min都是它本身;当有两个元素时,比较两个数的大小,大者为最大值max,小者为最小值min;当数组中元素多于两个时,里用分治法原理,递归调用MaxMin函数,求出划分出的每组中的最值与另外一组最值比较,最后的得出最大值max和最小值min。设计分析:分析数组中的元素:有一个元素、两个元素、两个以上元素(1) 最大值最小值都是同一个元素,不用判断直接赋值min
2、、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输出:程序及运行结果正误判断: 非常好 正确,还可改进 基本正确,还需改进 还有
3、错误 不足之处或设计经验小结: 任课教师评语:教师签字: 年月日程序设计课程上机实验报告注:每学期至少有一次设计性实验。每学期结束请任课教师按时按量统一交到教学秘书处。源程序文件名及组成文件:重要变量用途说明 算法描述#include /导入头文件using namespace std;template /template函数模板 class SortableList private: T *array; /定义数组,用来存储求最值的数组int maxSize; /定义数组长度public: SortableList();void SetMaxSize() coutmaxSize; /输入数组
4、长度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()dele
5、te 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.dispayArray();a.MaxMin(0,size,Max,Min);cout 最大元素为Max 最小元素为Minendl; system(pause);return 0;