姓名

学号

班级

时间

10.17

上午

地点

工训楼

309

实验名称

分治算法实验（用分治法查找数组元素的最大值和最小值）

实验目的

通过上机实验，要求掌握分治算法的问题描述、算法设计思想、程序设计。

实验原理

使用分治的算法，

根据不同的输入用例，

能准确的输出用例中的最大值与最小

值。并计算出程序运行所需要的时间。

程序思路：

利用分治法，

将一个数组元素大于

2

的数组分成两个子数组，

然后

对每一个子数组递归调用，直到最小的子数组的元素个数为

1

个或者是

2

个，

此时直接就能得出最大值与最小值，

然后合并子数组，

比较

2

个子数组的最大

值与最小值，依次进行下去，知道找到整个数组的最大值与最小值。

实验步骤

1.

先解决小规模的问题，

如数组中只有

 1 

个元素或者只有两个元素时候

的情况。

2.

将问题分解，

如果数组的元素大于等于

 3 

个，

将数组分为两个小的数

组。

3.

递归的解各子问题，

将中分解的两个小的数组再进行以上两个步骤最后都

化为小规模问题。

4.

将各子问题的解进行比较最终得到原问题的解。

关键代码

//

分治法处理整个数组，求出最大值与最小值

void

 merge(

int

 a[],

int

 left,

int

 right,

int

 &Max,

int

 &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=max1; 

//

子序列两两合并，求出最大值与最小值