python使用分治法實(shí)現(xiàn)求解最大值的方法
本文實(shí)例講述了python使用分治法實(shí)現(xiàn)求解最大值的方法。分享給大家供大家參考。具體分析如下：
題目：
給定一個(gè)順序表，編寫(xiě)一個(gè)求出其最大值和最小值的分治算法。
分析：
由于順序表的結(jié)構(gòu)沒(méi)有給出，作為演示分治法這里從簡(jiǎn)順序表取一整形數(shù)組數(shù)組大小由用戶(hù)定義，數(shù)據(jù)隨機(jī)生成。我們知道如果數(shù)組大小為 1 則可以直接給出結(jié)果，如果大小為 2則一次比較即可得出結(jié)果，于是我們找到求解該問(wèn)題的子問(wèn)題即: 數(shù)組大小 <= 2。到此我們就可以進(jìn)行分治運(yùn)算了，只要求解的問(wèn)題數(shù)組長(zhǎng)度比 2 大就繼續(xù)分治，否則求解子問(wèn)題的解并更新全局解以下是代碼。
題目看懂了就好說(shuō)了，關(guān)鍵是要把順序表分解成為k個(gè)元素為2的列表，然后找列表的最大值，然后把子問(wèn)題的列表進(jìn)行合并，再遞歸求解。
上代碼吧：
#-*- coding:utf-8 -*-
#分治法求解最大值問(wèn)題
import random
#求解兩個(gè)元素的列表的最大值方法
def max_value(max_list):
return max(max_list)
#定義求解的遞歸方法
def solve(init_list):
if len(init_list) <= 2:
#若列表元素個(gè)數(shù)小于等于2，則輸出結(jié)果
print max_value(init_list)
else:
init_list=[init_list[i:i+2] for i in range(0,len(init_list),2)]
#將列表分解為列表長(zhǎng)度除以2個(gè)列表
max_init_list = []
#用于合并求最大值的列表
for _list in init_list:
#將各各個(gè)子問(wèn)題的求解列表合并
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]
#測(cè)試列表
solve(test_list)
希望本文所述對(duì)大家的Python程序設(shè)計(jì)有所幫助。
相關(guān)文章
python引用(import)某個(gè)模塊提示沒(méi)找到對(duì)應(yīng)模塊的解決方法
今天小編就為大家分享一篇python引用(import)某個(gè)模塊提示沒(méi)找到對(duì)應(yīng)模塊的解決方法，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2019-01-01
python讀取相對(duì)路徑和絕對(duì)路徑的方法
這篇文章主要介紹了python讀取相對(duì)路徑和絕對(duì)路徑,下面的路徑介紹針對(duì)windows，在編寫(xiě)的py文件中打開(kāi)文件的時(shí)候經(jīng)常見(jiàn)到下面其中路徑的表達(dá)方式，需要的朋友可以參考下2023-02-02
這篇文章主要為大家介紹了Ubuntu安裝Python的實(shí)現(xiàn)過(guò)程詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2023-06-06
python中l(wèi)strip()截掉字符的實(shí)例講解
在本篇文章里小編給大家整理的是一篇關(guān)于python中l(wèi)strip()截掉字符的實(shí)例講解內(nèi)容，有興趣的朋友們可以學(xué)習(xí)下。2021-05-05
Python使用指定端口進(jìn)行http請(qǐng)求的例子
今天小編就為大家分享一篇Python使用指定端口進(jìn)行http請(qǐng)求的例子，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2019-07-07
本文主要介紹了pandas檢查和填充缺失值的N種方法總結(jié)，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2023-01-01
在本篇文章里小編給大家分享了關(guān)于Python列表的切片的知識(shí)點(diǎn)實(shí)例，需要的朋友們可以參考下。2019-08-08
turtle庫(kù)是Python語(yǔ)言中一個(gè)很流行的繪制圖像的函數(shù)庫(kù)，想象一個(gè)小烏龜，在一個(gè)橫軸為x、縱軸為y的坐標(biāo)系原點(diǎn)，(0,0)開(kāi)始，它根據(jù)一組函數(shù)指令的控制，在這個(gè)平面坐標(biāo)系中移動(dòng)，從而在它爬行的路徑上繪制了圖形，本文介紹Python繪圖模塊turtle，感興趣的朋友一起看看吧2023-01-01
Python Process創(chuàng)建進(jìn)程的2種方法詳解
這篇文章主要介紹了Python Process創(chuàng)建進(jìn)程的2種方法詳解,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2021-01-01
Python subprocess模塊學(xué)習(xí)總結(jié)
從Python 2.4開(kāi)始，Python引入subprocess模塊來(lái)管理子進(jìn)程，以取代一些舊模塊的方法：如 os.system、os.spawn*、os.popen*、popen2.*、commands.*不但可以調(diào)用外部的命令作為子進(jìn)程，而且可以連接到子進(jìn)程的input/output/error管道，獲取相關(guān)的返回信息2014-03-03