分治算法实验(用分治法查找数组元素的最大值和最小值)
- 格式：doc
- 大小：62.00 KB
- 文档页数：6
算法分析与设计实验报告第一次实验
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<iostream>
#include<time.h>
#include<iomanip>
using namespace std;
//当数组中的元素个数小于3时，处理最大值
int compmax(int A[],int start,int end) {
int max;
if(start<end) //有两个元素{
if(A[start]<=A[end])
max=A[end];
else
max=A[start];
}
else//有一个元素max=A[start];
return max;
}
//当数组中元素的个数小于2时，处理最小值
int compmin(int A[],int start,int end) {
int min;
if(start<end) //有两个元素{
if(A[start]<=A[end])
min=A[start];
else
min=A[end];
}
else//有一个元素
min=A[start];
return min;
}
//分治法处理整个数组，求最大值与最小值
void merge(int a[],int left,int right,int &Max,int &Min) //Max,Min 用来保存最大值与最小值
//之所以使用&引用，是由于如果只是简单的使用变量，并不会改变Max与Min的值，使用指针也可以
{
int max1=0,min1=0,max2=0,min2=0;
if(right-left>2) //当数组中元素个数大于等于3时，进行分治
{
int mid=(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);
}
}
void ran(int *input,int n) //随机生成数组元素函数
{
int i;
srand(time(0));
for(i=0;i<n;i++)
input[i]=rand();
input[i]='\0';
}
int a[1000000]; //定义全局变量用来存放要查找的数组
int main()
{
int n;
int i;
int max;
int min;
cout<<"请输入要查找的序列个数："<<endl;
for(i=0;i<5;i++)
{
cin>>n;
ran(a,n);
clock_t start,end,over; //计算程序运行时间的算法
start=clock();
end=clock();
over=end-start;
start=clock();
merge(a,0,n-1,max,min); //调用分治法算法
cout<<max<<" "<<min<<endl;
end=clock();
printf("The time is %6.3f",(double)(end-start-over)/CLK_TCK); //显示运行时间
}
system("pause"); //停止运行窗口
return 0;
}
完整代码（非递归方法）
#include<iostream>
#include<time.h>
#include<iomanip>
using namespace std;
void ran(int *input,int n) //随机生成数组元素函数
{
int i;
srand(time(0));
for(i=0;i<n;i++)
input[i]=rand();
input[i]='\0';
}
int a[1000000];
int main()
{
int max=a[0],min=a[0];
int i,j,n;
cout<<"请输入数据规模："<<endl;
for(j=0;j<5;j++)
{
cin>>n;
ran(a,n);
clock_t start,end,over; //计算程序运行时间的算法
start=clock();
end=clock();
over=end-start;
start=clock();
for(i=1;i<n;i++)
{
if(a[i]>max)
max=a[i];
if(a[i]<min)
min=a[i];
}
cout<<max<<" "<<min<<endl;
end=clock();
printf("The time is %6.3f",(double)(end-start-over)/CLK_TCK); //显示运行时间
}
system("pause");
return 0;
}。
