python使用分治法实现求解最大值的方法
作者:BlackImpl 时间:2021-07-14 12:06:09
本文实例讲述了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程序设计有所帮助。
标签:python,分治法,最大值
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
WEB前端开发规范文档
2010-10-19 12:32:00
如何让shell终端和goland控制台输出彩色的文字
2023-07-13 03:24:56
![](https://img.aspxhome.com/file/2023/9/87629_0s.jpg)
python 识别图片中的文字信息方法
2022-06-06 15:32:05
![](https://img.aspxhome.com/file/2023/6/65066_0s.jpg)
Javascript与PHP验证用户输入URL地址是否正确
2023-10-23 02:36:07
css学习笔记:div在IE6下无法遮盖select
2009-04-30 13:21:00
![](https://img.aspxhome.com/file/UploadPic/20094/30/11f2ae205c6g215-66s.jpg)
PHP操作MySQL中BLOB字段的方法示例【存储文本与图片】
2023-11-23 23:45:27
Quickwork For Asp -实战之后台管理
2009-12-31 19:13:00
![](https://img.aspxhome.com/file/UploadPic/20101/11/2010111171421531s.jpg)
用Dreamweaver设计实现网页过渡转换功能
2008-09-04 10:09:00
![](https://img.aspxhome.com/file/uploadpic/20072/200723113553118.jpg)
Python pandas中read_csv参数示例详解
2021-05-14 06:17:12
![](https://img.aspxhome.com/file/2023/3/69623_0s.png)
[译]“我心中的ebay”
2008-06-04 12:09:00
![](https://img.aspxhome.com/file/UploadPic/20086/4/200864121043106s.jpg)
使用go gin来操作cookie的讲解
2023-09-12 14:21:49
如何动态产生变量?
2009-11-18 16:33:00
木鸟:ASP缓存类无错版
2008-02-20 12:53:00
Python基础知识学习之类的继承
2022-09-02 15:41:05
浅谈购物类网站如何保持视觉设计的一致性
2009-03-30 16:02:00
![](https://img.aspxhome.com/file/UploadPic/20093/30/14-52s.jpg)
php mailer类调用远程SMTP服务器发送邮件实现方法
2023-08-16 16:09:18
CSS Position
2009-05-17 14:27:00
![](https://img.aspxhome.com/file/UploadPic/20095/17/static-15s.png)
SQL学习笔记四 聚合函数、排序方法
2011-09-30 11:33:29
JS代码格式化和语法着色
2013-07-14 19:47:45
WEB设计经验-来自Microsoft
2008-05-15 07:30:00