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)

相关推荐

  • 用Python实现通过哈希算法检测图片重复的教程

    用Python实现通过哈希算法检测图片重复的教程

    Iconfinder 是一个图标搜索引擎,为设计师.开发者和其他创意工作者提供精美图标,目前托管超过 34 万枚图标,是全球最大的付费图标库.用户也可以在 Iconfinder 的交易板块上传出售原创作品.每个月都有成千上万的图标上传到Iconfinder,同时也伴随而来大量的盗版图.Iconfinder 工程师 Silviu Tantos 在本文中提出一个新颖巧妙的图像查重技术,以杜绝盗版. 我们将在未来几周之内推出一个检测上传图标是否重复的功能.例如,如果用户下载了一个图标然后又试图通过上传

  • python使用rsa加密算法模块模拟新浪微博登录

    PC登录新浪微博时,在客户端用js预先对用户名.密码都进行了加密,而且在POST之前会GET一组参数,这也将作为POST_DATA的一部分.这样,就不能用通常的那种简单方法来模拟POST登录(比如人人网). 通过爬虫获取新浪微博数据,模拟登录是必不可少的. 1.在提交POST请求之前,需要GET获取四个参数(servertime,nonce,pubkey和rsakv),不是之前提到的只是获取简单的servertime,nonce,这里主要是由于js对用户名.密码加密方式改变了. 1.1 由于加密

  • python k-近邻算法实例分享

    简单说明 这个算法主要工作是测量不同特征值之间的距离,有个这个距离,就可以进行分类了. 简称kNN. 已知:训练集,以及每个训练集的标签. 接下来:和训练集中的数据对比,计算最相似的k个距离.选择相似数据中最多的那个分类.作为新数据的分类. python实例 复制代码 代码如下: # -*- coding: cp936 -*- #win系统中应用cp936编码,linux中最好还是utf-8比较好.from numpy import *#引入科学计算包import operator #经典pyt

  • Python聚类算法之凝聚层次聚类实例分析

    Python聚类算法之凝聚层次聚类实例分析

    本文实例讲述了Python聚类算法之凝聚层次聚类.分享给大家供大家参考,具体如下: 凝聚层次聚类:所谓凝聚的,指的是该算法初始时,将每个点作为一个簇,每一步合并两个最接近的簇.另外即使到最后,对于噪音点或是离群点也往往还是各占一簇的,除非过度合并.对于这里的"最接近",有下面三种定义.我在实现是使用了MIN,该方法在合并时,只要依次取当前最近的点对,如果这个点对当前不在一个簇中,将所在的两个簇合并就行: 单链(MIN):定义簇的邻近度为不同两个簇的两个最近的点之间的距离. 全链(MAX

  • python实现RSA加密(解密)算法

    python实现RSA加密(解密)算法

    RSA是目前最有影响力的公钥加密算法,它能够抵抗到目前为止已知的绝大多数密码攻击,已被ISO推荐为公钥数据加密标准. 今天只有短的RSA钥匙才可能被强力方式解破.到2008年为止,世界上还没有任何可靠的攻击RSA算法的方式.只要其密钥的长度足够长,用RSA加密的信息实际上是不能被解破的.但在分布式计算和量子计算机理论日趋成熟的今天,RSA加密安全性受到了挑战. RSA算法基于一个十分简单的数论事实:将两个大素数相乘十分容易,但是想要对其乘积进行因式分解却极其困难,因此可以将乘积公开作为加密密钥.

  • python编写的最短路径算法

    python编写的最短路径算法

    一心想学习算法,很少去真正静下心来去研究,前几天趁着周末去了解了最短路径的资料,用python写了一个最短路径算法.算法是基于带权无向图去寻找两个点之间的最短路径,数据存储用邻接矩阵记录.首先画出一幅无向图如下,标出各个节点之间的权值. 其中对应索引: A --> 0 B--> 1 C--> 2 D-->3 E--> 4 F--> 5 G--> 6 邻接矩阵表示无向图: 算法思想是通过Dijkstra算法结合自身想法实现的.大致思路是:从起始点开始,搜索周围的路径

  • Python基于DES算法加密解密实例

    本文实例讲述了Python基于DES算法加密解密实现方法.分享给大家供大家参考.具体实现方法如下: #coding=utf-8 from functools import partial import base64 class DES(object): """ DES加密算法 interface: input_key(s, base=10), encode(s), decode(s) """ __ip = [ 58,50,42,34,26,18,

  • Python算法之栈（stack）的实现

    本文以实例形式展示了Python算法中栈(stack)的实现,对于学习数据结构域算法有一定的参考借鉴价值.具体内容如下: 1.栈stack通常的操作: Stack() 建立一个空的栈对象 push() 把一个元素添加到栈的最顶层 pop() 删除栈最顶层的元素,并返回这个元素 peek()  返回最顶层的元素,并不删除它 isEmpty()  判断栈是否为空 size()  返回栈中元素的个数 2.简单案例以及操作结果: Stack Operation Stack Contents Return

  • Python分治法定义与应用实例详解

    本文实例讲述了Python分治法定义与应用.分享给大家供大家参考,具体如下: 分治法所能解决的问题一般具有以下几个特征: 1) 该问题的规模缩小到一定的程度就可以容易地解决 2) 该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质. 3) 利用该问题分解出的子问题的解可以合并为该问题的解: 4) 该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子子问题. 第一条特征是绝大多数问题都可以满足的,因为问题的计算复杂性一般是随着问题规模的增加而增加: 第二条特征是应用

  • Python实现的Kmeans++算法实例

    1.从Kmeans说起 Kmeans是一个非常基础的聚类算法,使用了迭代的思想,关于其原理这里不说了.下面说一下如何在matlab中使用kmeans算法. 创建7个二维的数据点: 复制代码 代码如下: x=[randn(3,2)*.4;randn(4,2)*.5+ones(4,1)*[4 4]]; 使用kmeans函数: 复制代码 代码如下: class = kmeans(x, 2); x是数据点,x的每一行代表一个数据:2指定要有2个中心点,也就是聚类结果要有2个簇. class将是一个具有7

  • python实现simhash算法实例

    python实现simhash算法实例

    Simhash的算法简单的来说就是,从海量文本中快速搜索和已知simhash相差小于k位的simhash集合,这里每个文本都可以用一个simhash值来代表,一个simhash有64bit,相似的文本,64bit也相似,论文中k的经验值为3.该方法的缺点如优点一样明显,主要有两点,对于短文本,k值很敏感:另一个是由于算法是以空间换时间,系统内存吃不消. 复制代码 代码如下: #!/usr/bin/python# coding=utf-8class simhash: #构造函数    def __

  • 朴素贝叶斯算法的python实现方法

    朴素贝叶斯算法的python实现方法

    本文实例讲述了朴素贝叶斯算法的python实现方法.分享给大家供大家参考.具体实现方法如下: 朴素贝叶斯算法优缺点 优点:在数据较少的情况下依然有效,可以处理多类别问题 缺点:对输入数据的准备方式敏感 适用数据类型:标称型数据 算法思想: 比如我们想判断一个邮件是不是垃圾邮件,那么我们知道的是这个邮件中的词的分布,那么我们还要知道:垃圾邮件中某些词的出现是多少,就可以利用贝叶斯定理得到. 朴素贝叶斯分类器中的一个假设是:每个特征同等重要 函数 loadDataSet() 创建数据集,这里的数据集

随机推荐