python使用分治法实现求解最大值的方法

yipeiwu_com7年前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程序设计有所帮助。

相关文章

在Python下进行UDP网络编程的教程

在Python下进行UDP网络编程的教程

TCP是建立可靠连接,并且通信双方都可以以流的形式发送数据。相对TCP,UDP则是面向无连接的协议。 使用UDP协议时,不需要建立连接,只需要知道对方的IP地址和端口号,就可以直接发数据...

Python实现的视频播放器功能完整示例

本文实例讲述了Python实现的视频播放器功能。分享给大家供大家参考,具体如下: # -*- coding:utf-8 -*- #! python3 # --------------...

python获取全国城市pm2.5、臭氧等空气质量过程解析

随着国家发展,中国很多城市的空气质量其实并不好,国家气象局会有实时统计,但是要去写爬虫爬取是十分麻烦的事情,并且官方网站也会做一些反爬虫措施,所以实现起来比较麻烦,最好的办法就是使用现成...

利用matplotlib+numpy绘制多种绘图的方法实例

利用matplotlib+numpy绘制多种绘图的方法实例

前言 matplotlib 是Python最著名的绘图库,它提供了一整套和matlab相似的命令API,十分适合交互式地进行制图。本文将以例子的形式分析matplot中支持的,分析中常用...

python实现对象列表根据某个属性排序的方法详解

本文实例讲述了python实现对象列表根据某个属性排序的方法。分享给大家供大家参考,具体如下: 对于一个已有的python list, 里面的内容是一些对象,这些对象有一些相同的属性值,...