时间:2021-05-22
本文实例讲述了python使用分治法实现求解最大值的方法。分享给大家供大家参考。具体分析如下:
题目:
给定一个顺序表,编写一个求出其最大值和最小值的分治算法。
分析:
由于顺序表的结构没有给出,作为演示分治法这里从简顺序表取一整形数组数组大小由用户定义,数据随机生成。我们知道如果数组大小为 1 则可以直接给出结果,如果大小为 2则一次比较即可得出结果,于是我们找到求解该问题的子问题即: 数组大小 <= 2。到此我们就可以进行分治运算了,只要求解的问题数组长度比 2 大就继续分治,否则求解子问题的解并更新全局解以下是代码。
题目看懂了就好说了,关键是要把顺序表分解成为k个元素为2的列表,然后找列表的最大值,然后把子问题的列表进行合并,再递归求解。
上代码吧:
#-*- coding:utf-8 -*-#分治法求解最大值问题import random#求解两个元素的列表的最大值方法def max_value(max_list): return max(max_list)#定义求解的递归方法def solve(init_list): if len(init_list) <= 2: #若列表元素个数小于等于2,则输出结果 print max_value(init_list) else: init_list=[init_list[i:i+2] for i in range(0,len(init_list),2)] #将列表分解为列表长度除以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程序设计有所帮助。
声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。
本文为大家分享了C语言实现分治法实例代码,供大家参考,具体内容如下使用分治法求最大值这个函数将数组a[l]...a[r]分成a[l],...,a[m]和a[m+
Python中的最大整数Python中可以通过sys模块来得到int的最大值.python2中使用的方法是importsysmax=sys.maxintprin
在python中利用numpy创建一个array,然后我们想获取array的最大值,最小值。可以使用一下方法:一、创建数组这样就可以获得一个array的最大值和
有一道算法题题目的意思是在二维数组里找到一个峰值。要求复杂度为n。解题思路是找田字(四边和中间横竖两行)中最大值,用分治法递归下一个象限的田字。在用python
快速排序法主要是运用了Arrays中的一个方法Arrays.sort()实现。冒泡法是运用遍历数组进行比较,通过不断的比较将最小值或者最大值一个一个的遍历出来。