python使用分治法实现求解最大值的方法
作者:BlackImpl 发布时间:2021-07-14 12:06:09
标签:python,分治法,最大值
本文实例讲述了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程序设计有所帮助。
0
投稿
猜你喜欢
- 本文实例讲述了PHP自定义函数格式化json数据的方法。分享给大家供大家参考,具体如下:<?php /**
- 最近学习python并发,于是对多进程、多线程、异步和协程做了个总结。一、多线程多线程就是允许一个进程内存在多个控制权,以便让多个函数同时处
- 有很多应用项目, 刚起步的时候用MYSQL数据库基本上能实现各种功能需求,随着应用用户的增多,数据量的增加,MYSQL渐渐地出现不堪重负的情
- 【尝尝管理员的滋味】- 淡然看,其实一切都很简单IE的滤镜泄露是最大的危害,没有找到方法解决,所以禁用了滤镜。<!DOCTYPE ht
- 在软件开发的初始阶段,开发商们总是想把整个系统的最小的细节设计好了,然后再去单线程的编写代码。这样软件开发完成需要很长时间,但开发商们一直都
- 由于 window.onload 事件需要在页面所有内容(包括图片等)加载完后,才执行,但往往我们更希望在 DOM 一加载完就执行脚本。其实
- 什么是索引拿汉语字典的目录页(索引)打比方:正如汉语字典中的汉字按页存放一样,SQL Server中的数据记录也是按页存放的,每页容量一般为
- 一、问题描述当用JS调用form的方法submit直接提交form的时候,submit事件不响应。为什么?知道的请回复。类比一下,我用inp
- 查询速度慢的原因很多,常见如下几种:1、没有索引或者没有用到索引(这是查询慢最常见的问题,是程序设计的缺陷)2、I/O吞吐量小,形成了瓶颈效
- UCD介绍UCD是Unicode字符数据库(Unicode Character DataBase)的缩写。UCD由一些描述Unicode字符
- 1.linux下启动mysql的命令:mysqladmin start/ect/init.d/mysql start (前面为mysql的安
- 大名鼎鼎的FCKeditor终于在最近发布新版本了,与增加版本号不同,这次完全把它改名了,更名为CKeditor。这应该是和它的开发公司CK
- 最近老婆大人的公司给老婆大人安排了一个根据关键词查询google网站排名的差事。老婆大人的公司是做seo的,查询的关键词及网站特别的多,看着
- 1. 加载数据集这次我们搭建一个小小的多层线性网络对糖尿病的病例进行分类首先先导入需要的库文件先来看看我们的数据集观察可以发现,前八列是我们
- <script language="javascript"><!-- var&n
- 扪心自问,你真正了解你卖给用户的是什么玩意么?你所认为革命性的,一定会震惊世界的功能、特色,用户真的买单么?我的意思是,我们总是习惯性的忘记
- 本文实例讲述了Python实现获取邮箱内容并解析的方法。分享给大家供大家参考,具体如下:# -*- coding: utf-8 -*-fro
- 在应用系统开发初期,由于开发数据库数据比较少,对于查询SQL语句,复杂视图的编写,刚开始不会体会出SQL语句各种写法的性能优劣,但是如果将应
- 引言 性能是一个特征。您必须预先设计性能,否则您以后就得重写应用程序。就是说,有哪些好的策略可使 Active Server Pages (
- asp之家注:学习asp网页编程的朋友一定用过ACCESS数据库,access的简单方便,大大降低了asp初学者学习asp的门槛,对于学习a