python使用分治法实现求解最大值的方法
本文实例讲述了python使用分治法实现求解最大值的方法。分享给大家供大家参考。具体分析如下：
题目：
给定一个顺序表，编写一个求出其最大值和最小值的分治算法。
分析：
由于顺序表的结构没有给出，作为演示分治法这里从简顺序表取一整形数组数组大小由用户定义，数据随机生成。我们知道如果数组大小为1则可以直接给出结果，如果大小为2则一次比较即可得出结果，于是我们找到求解该问题的子问题即:数组大小<=2。到此我们就可以进行分治运算了，只要求解的问题数组长度比2大就继续分治，否则求解子问题的解并更新全局解以下是代码。
题目看懂了就好说了，关键是要把顺序表分解成为k个元素为2的列表，然后找列表的最大值，然后把子问题的列表进行合并，再递归求解。
上代码吧：
#-*-coding:utf-8-*- #分治法求解最大值问题 importrandom #求解两个元素的列表的最大值方法 defmax_value(max_list): returnmax(max_list) #定义求解的递归方法 defsolve(init_list): iflen(init_list)<=2: #若列表元素个数小于等于2，则输出结果 printmax_value(init_list) else: init_list=[init_list[i:i+2]foriinrange(0,len(init_list),2)] #将列表分解为列表长度除以2个列表 max_init_list=[] #用于合并求最大值的列表 for_listininit_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程序设计有所帮助。