分治算法实验用分治法查找数组元素的最大值和最小值.doc
《分治算法实验用分治法查找数组元素的最大值和最小值.doc》由会员分享，可在线阅读，更多相关《分治算法实验用分治法查找数组元素的最大值和最小值.doc（6页珍藏版）》请在冰点文库上搜索。
算法分析与设计实验报告
第一次实验
姓名
学号
班级
时间
10.17上午
地点
工训楼309
实验名称
分治算法实验（用分治法查找数组元素的最大值和最小值）
实验目的
通过上机实验，要求掌握分治算法的问题描述、算法设计思想、程序设计。
实验原理
使用分治的算法，根据不同的输入用例，能准确的输出用例中的最大值与最小值。
并计算出程序运行所需要的时间。
程序思路：
利用分治法，将一个数组元素大于2的数组分成两个子数组，然后对每一个子数组递归调用，直到最小的子数组的元素个数为1个或者是2个，此时直接就能得出最大值与最小值，然后合并子数组，比较2个子数组的最大值与最小值，依次进行下去，知道找到整个数组的最大值与最小值。
实验步骤
1.先解决小规模的问题，如数组中只有1个元素或者只有两个元素时候的情况。
2.将问题分解，如果数组的元素大于等于3个，将数组分为两个小的数组。
3.递归的解各子问题，将中分解的两个小的数组再进行以上两个步骤最后都化为小规模问题。
4.将各子问题的解进行比较最终得到原问题的解。
关键代码
//分治法处理整个数组，求出最大值与最小值
voidmerge（inta[],intleft,intright,int&Max,int&Min）
{
intmax1=0,min1=0,max2=0,min2=0;
if（right-left>2）//当数组中元素个数大于3时，才实行分治法
{
intmid=（right+left）/2;
merge（a,left,mid,max1,min1）;
//左半边递归调用自身，求出最大值与最小值，分别保存在max1,min1中
merge（a,mid+1,right,max2,min2）;
//右半边递归调用自身，求出最大值与最小值，分别保存在max2,min2中
if（max1>=max2）
Max=max1;//子序列两两合并，求出最大值与最小值
else
Max=max2;//分别保存在Max与Min
if（min1<=min2）
Min=min1;
else
Min=min2;
}
else//当数组中元素个数少于2时，直接赋值处理
{
Max=compmax（a,left,right）;
Min=compmin（a,left,right）;
}
}
测试结果
利用分治法（递归实现）：
非递归实现：
实验心得
通过这次实验，加深了我对分治法的理解，明白了分治法到底是怎样的一个过程，在代码实现分治法的时候，也使我加深了对于自己构造函数的理解，明白了分治法利用代码是怎样实现的，以及构造函数的传参与返回值等等地方需要注意的东西，是我认识到我的编程能力的不足，更加加深了我要好好学习，多做练习的想法，总体收获很大。
实验比较
观察上面两个不同的实现方法所花费的时间，我们可以看到，采用非递归的方法实现，所花费的时间比利用分治法花费的时间多，为什么会出现这样的结果，我们可以知道在分治法需要比较的次数比非递归方法多，甚至是多得多，所以它所花费的时间也多，所以对于这种求最大值最小值的问题，利用非递归的方法相对会好一点。
实验得分
助教签名
附录：
完整代码（分治法）
#include
#include
#include
usingnamespacestd;
//当数组中的元素个数小于3时，处理最大值
intcompmax（intA[],intstart,intend）
{
intmax;
if（start {
if（A[start]<=A[end]）
max=A[end];
else
max=A[start];
}
else//有一个元素
max=A[start];
returnmax;
}
//当数组中元素的个数小于2时，处理最小值
intcompmin（intA[],intstart,intend）
{
intmin;
if（start {
if（A[start]<=A[end]）
min=A[start];
else
min=A[end];
}
else//有一个元素
min=A[start];
returnmin;
}
//分治法处理整个数组，求最大值与最小值
voidmerge（inta[],intleft,intright,int&Max,int&Min）//Max,Min用来保存最大值与最小值
//之所以使用&引用，是由于如果只是简单的使用变量，并不会改变Max与Min的值，使用指针也可以
{
intmax1=0,min1=0,max2=0,min2=0;
if（right-left>2）//当数组中元素个数大于等于3时，进行分治
{
intmid=（right+left）/2;
merge（a,left,mid,max1,min1）;//左半边递归调用自身，求出最大值最小值，分别保存在max1,min1中
merge（a,mid+1,right,max2,min2）;//右半边递归调用自身，求出最大值最小值，分别保存在max2,min2中
if（max1>=max2）//子序列两两合并，求出最大值与最小值，保存在Max与Min中
Max=max1;
else
Max=max2;
if（min1<=min2）
Min=min1;
else
Min=min2;
}
else//数组中元素个数小于3时的情况，直接赋值
{
Max=compmax（a,left,right）;
Min=compmin（a,left,right）;
}
}
voidran（int*input,intn）//随机生成数组元素函数
{
inti;
srand（time（0））;
for（i=0;i input[i]=rand（）;
input[i]='\0';
}
inta[1000000];//定义全局变量用来存放要查找的数组
intmain（）
{
intn;
inti;
intmax;
intmin;
cout<<"请输入要查找的序列个数：
"< for（i=0;i<5;i++）
{
cin>>n;
ran（a,n）;
clock_tstart,end,over;//计算程序运行时间的算法
start=clock（）;
end=clock（）;
over=end-start;
start=clock（）;
merge（a,0,n-1,max,min）;//调用分治法算法
cout< end=clock（）;
printf（"Thetimeis%6.3f",（double）（end-start-over）/CLK_TCK）;//显示运行时间
}
system（"pause"）;//停止运行窗口
return0;
}
完整代码（非递归方法）
#include
#include
#include
usingnamespacestd;
voidran（int*input,intn）//随机生成数组元素函数
{
inti;
srand（time（0））;
for（i=0;i input[i]=rand（）;
input[i]='\0';
}
inta[1000000];
intmain（）
{
intmax=a[0],min=a[0];
inti,j,n;
cout<<"请输入数据规模：
"< for（j=0;j<5;j++）
{
cin>>n;
ran（a,n）;
clock_tstart,end,over;//计算程序运行时间的算法
start=clock（）;
end=clock（）;
over=end-start;
start=clock（）;
for（i=1;i {
if（a[i]>max）
max=a[i];
if（a[i] min=a[i];
}
cout< end=clock（）;
printf（"Thetimeis%6.3f",（double）（end-start-over）/CLK_TCK）;//显示运行时间
}
system（"pause"）;
return0;
}
升级会员 