作者:jueduiliu | 来源:互联网 | 2018-07-18 17:53
本文实例讲述了python使用分治法实现求解最大值的方法。分享给大家供大家参考。具体分析如下:
题目:
给定一个顺序表,编写一个求出其最大值和最小值的分治算法。
分析:
由于顺序表的结构没有给出,作为演示分治法这里从简顺序表取一整形数组数组大小由用户定义,数据随机生成。我们知道如果数组大小为 1 则可以直接给出结果,如果大小为 2则一次比较即可得出结果,于是我们找到求解该问题的子问题即: 数组大小 <= 2。到此我们就可以进行分治运算了,只要求解的问题数组长度比 2 大就继续分治,否则求解子问题的解并更新全局解以下是代码。
题目看懂了就好说了,关键是要把顺序表分解成为k个元素为2的列表,然后找列表的最大值,然后把子问题的列表进行合并,再递归求解。
上代码吧:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | import random
def max_value(max_list):
return max (max_list)
def solve(init_list):
if len (init_list) < = 2 :
print max_value(init_list)
else :
init_list = [init_list[i:i + 2 ] for i in range ( 0 , len (init_list), 2 )]
max_init_list = []
for _list in init_list:
max_init_list.append(max_value(_list))
solve(max_init_list)
if __name__ = = "__main__" :
test_list = [ 12 , 2 , 23 , 45 , 67 , 3 , 2 , 4 , 45 , 63 , 24 , 23 ]
solve(test_list)
|
希望本文所述对大家的Python程序设计有所帮助。