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)文章
這篇文章主要為大家詳細(xì)介紹了如何基于PyQt制作一個(gè)小紅書(shū)圖片抓取工具,文中的示例代碼講解詳細(xì),具有一定的借鑒價(jià)值,感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2023-11-11
Python PyQt5實(shí)戰(zhàn)項(xiàng)目之網(wǎng)速監(jiān)控器的實(shí)現(xiàn)
PyQt5以一套Python模塊的形式來(lái)實(shí)現(xiàn)功能。它包含了超過(guò)620個(gè)類(lèi)，600個(gè)方法和函數(shù)。它是一個(gè)多平臺(tái)的工具套件，它可以運(yùn)行在所有的主流操作系統(tǒng)中，包含Unix，Windows和Mac OS。PyQt5采用雙重許可模式。開(kāi)發(fā)者可以在GPL和社區(qū)授權(quán)之間選擇2021-11-11
自學(xué)python求已知DNA模板的互補(bǔ)DNA序列
這篇文章主要為大家介紹了自學(xué)python求已知DNA模板的互補(bǔ)DNA序列的示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-06-06
Python中通過(guò)property設(shè)置類(lèi)屬性的訪(fǎng)問(wèn)
為了達(dá)到類(lèi)似C++類(lèi)的封裝性能,可以使用property來(lái)設(shè)置Python類(lèi)屬性的訪(fǎng)問(wèn)權(quán)限,本文就介紹一下Python中通過(guò)property設(shè)置類(lèi)屬性的訪(fǎng)問(wèn),感興趣的可以了解一下,感興趣的可以了解一下2023-09-09
Python利用fastapi實(shí)現(xiàn)上傳文件
FastAPI是一個(gè)現(xiàn)代的，快速（高性能）python?web框架。本文將利用fastapi實(shí)現(xiàn)上傳文件功能，文中的示例代碼講解詳細(xì)，需要的可以參考一下2022-06-06
python實(shí)現(xiàn)二級(jí)登陸菜單及安裝過(guò)程
這篇文章主要介紹了python實(shí)現(xiàn)二級(jí)登陸菜單及安裝過(guò)程,，本文圖文并茂給大家介紹的非常詳細(xì)，具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2019-06-06
這篇文章主要介紹了Pandas如何提取非空行值問(wèn)題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2024-09-09
Anaconda下Python中h5py與netCDF4模塊下載與安裝的教程詳解
這篇文章主要為大家詳細(xì)介紹了基于Anaconda,下載并安裝Python中h5py與netCDF4這兩個(gè)模塊的方法,感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2024-01-01
這篇文章主要為大家詳細(xì)介紹了如何利用Python實(shí)現(xiàn)處理圖片水印的相關(guān)資料，主要是實(shí)現(xiàn)圖片水印的去除效果，感興趣的小伙伴可以嘗試一下2023-01-01
Python導(dǎo)出數(shù)據(jù)到Excel可讀取的CSV文件的方法
這篇文章主要介紹了Python導(dǎo)出數(shù)據(jù)到Excel可讀取的CSV文件的方法,設(shè)計(jì)Python操作Excel的相關(guān)技巧,需要的朋友可以參考下2015-05-05