python求最大值最小值_用分治法查找数组元素的最大值和最小值(python)

课程名称

计算机算法

实验课时

实验项目

名称

和序号

分治算法实验（用分治法查找数组元

素的最大值和最小值）

同组者

姓

名

实验目的

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

同时，加深我们对分治算法的理解。

实验环境

Python 3.6

Pycharm

实验内容

和原理

1.

实验内容：

在满足分治法的条件下，根据不同的输入用例，能准确的输出用例中的最

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

2.

实验原理：

用分治法查找数组元素的最大值和最小值。

实验步骤

方

法

关键代码

1.

实验步骤

①

先解决小规模的问题，如数组中只有

1

个元素或者只有两个元素时候的情况。

②

将问题分解，如果数组的元素大于等于

3

个，将数组分为两个小的数组。

③

递归的解各子问题，将

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

规模问题。

④

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

2.

实验方法：

以递归的方式对分治后的各个部分的结果进行处理，即把各部分的最大值比较得

到较大部分的最大值，依次最终得到完整

array

的最大值。

3.

关键代码

def Merge_Max(left,right):

global array #

需要求最大值的数组

if(len(array) <= 0): #

若数组为空，返回

return 0

if(right-left <= 1): #

已分解至最小单元，取最大值

if(array[left] >= array[right]):

max = array[left]

else:

max = array[right]