分治法最大值最小值 付添04113035_19847.doc

《算法设计与分析》 上 机 实 验 报 告 专 业 软件工程 班 级 软件1101班 学 号 学生姓名 付添 完成日期 【排版说明】Times New Roman字体。 （4）正文行距建议设置为1.5倍行距。 （5）实验报告中有图、表的，图、表格式必须标准，有编号，有标题。如下所示（图的标题在下方、表的标题在上方）： 图1 XXXXXXX图 表1 XXXXXXX表 数据1 数据2 数据3 数据4 数据5 …… …… …… …… …… 1. 上机题目及实验环境 1.1上机题目：用分治法查找数组元素的最大值和最小值。 1.2实验环境： CPU： 内存： 操作系统：xp 软件平台：vc6.0 2. 算法设计与分析 基本思想 分治法是最为重要的算法设计方法之一。 主要思想是：将一个问题不断分割成若干个小问题，然后通过对小问题的求解再生成大问题的解。 因此分治法可以分为两个重要步骤： （1）自顶向下：将问题不断分割成小的问题。 （2）自底而上：将小问题解决来构建大问题的解。 分治和递归经常同时应用在算法设计中。 算法设计 (1）将数据集 S 均分为 S1 和 S2； （2）求解 S1 和 S2 中的最大和最小值； （3）最终的最大和最小值可以计算得到：min( S1, S2 ), max( S1, S2 )； （4）采用同样的处理方法递归处理 S1 和 S2。 min_max(S, min, max) { if |S| = 2 then min ( min(S) max ( max(S) else split S evenly into S1 and S2 min_max(S1, min1, max1) min_max(S2, min2, max2) min ( min(min1, min2) max ( max(max1, max2) } 给出具体的原理，算法设计与分析细节等。 核心代码 void min_max(int arry[],int i,int j,int *min,int *max)//找出最大值和最小值 { int mid,min1,min2,max1,max2; if(i==j) { *max=arry[i]; *min=arry[i]; } else { if(j==i+1) if(arry[i]arry[j]) { *min=arry[j]; *max=arry[i]; } else { *min=arry[i]; *max=arry[j]; } else { mid=(i+j+1)/2; min_max(arry,i,mid,min1,max1); min_max(arry,mid+1,j,min2,max2); *min = min1min2 ? min1:min2; *max = max1max2 ? max1:max2; } } 在main函数中通过产生随机数给出数据通过调用min_max函数实现找出最大值，最小值并把他们返回main（）函数输出。 4. 运行与调试 给出程序的运行结果。建议给出不同情况下的运行结果并加以比较（如排序算法可以给出输入数据规模不等时的运行结果比较，如数组规模为100时的实验结果、数组规模为1000时的实验结果、数组规模为10000时的实验结果等）。程序运行有屏幕输出的，应给出屏幕截图。 图1 显示随机产生100个0到100个整数 找出了之间的最大值和最小值 图2 显示随机产生1000个0到100个整数 找出了之间的最大值和最小值 图3 显示随机产生10个0到100个整数 找出了之间的最大值和最小值 图1 图2 图3 5. 结果分析和小结 （1）对结果的分析。分析结果可以采用图或者表的形式给出。 运行时由于没有加随机数初始化函数 srand(time(0));每次运行结果都一样 这个问题在设计代码时由于时间匆忙也没有发现 知道被老师检查时 被老师发现 ，以致于我以后再也不会犯这个错误了。 本次上机实验的收获、心得体会。 上机可以督促我自己写代码 每次上机前我都会先把代码大致写好，上机是运行并检查错误，这样不仅提高我的写代码能力，同时对算法这门课也有了更深