分治法求最大最小值

一. 实验目的及实验环境

实验目的：加深对分治算法原理及实现过程的理解。 实验环境：VC++6.0 二. 实验内容

用分治法求数组中最大元素和最小元素。

三．方案设计

如果数组大小为 1 则可以直接给出结果，如果大小为 2则一次比较即可结果，于是我们找到求解该问题的子问题即: 数组大小 <= 2。到此我们就可以进行分治运算了，只要求解的问题数组长度比 2 大就继续分治，否则求解子问题的解并更新全局解。

四．测试数据及运行结果

五．总结

1． 实验过程中遇到的问题及解决办法

在刚开始的时候由于对分治法只是理论上的理解，并没有真的实际操作，所以不是很会，在写代码的时候有点困难，在参考书上例子自己思考之后就有思路了。

2． 对设计及调试过程的心得体会。

通过这次上机实验，自己从设计方案到代码的实现，虽然费了一些时间，但是总归弄清了分治法的思想，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之所以在以后的学习过程中自己一定要学以致用，只有自己亲手实践了才会理解更深刻，知识才会掌握更牢固。在考虑问题是一定要严谨，注意细节，设计好方案才是实现算法的关键，同时以后要增加自己的知识面。

六．附录：源代码（电子版）

#include using namespace std;

void min_max(int a[],int i,int j,int &min,int &max) {

int mid,max1,max2,min1,min2; if(i==j){ max=a[i]; min=a[i]; return ; }

if(j==i+1) {

if(a[i]>a[j]){min=a[j];max=a[i];} else{min=a[i];max=a[j];} } else {

mid=(i+j)/2;

min_max(a,i,mid,min1,max1); min_max(a,mid+1,j,min2,max2); if(min1>min2)min=min2; else min=min1;

if(max1>max2)max=max1; else max=max2; } }

int main() {

int n,m,a[100],min,max; cin>>n;

while(n!=0) {

cin>>m;

for(int i=1;i<=m;i++)cin>>a[i]; min_max(a,1,m,min,max); cout<

return 0; }

西 安 邮 电 大 学

（计算机学院）

课内实验报告

实验名称： 分治法求最值

专业名称： 计科 班 级： 学生姓名：

学号（8位）： 指导教师： 刘伟 实验日期： 2015年 月 日