本文實(shí)例講述了Python分治法定義與應(yīng)用。分享給大家供大家參考，具體如下：

分治法所能解決的問題一般具有以下幾個(gè)特征：

1) 該問題的規(guī)模縮小到一定的程度就可以容易地解決
2) 該問題可以分解為若干個(gè)規(guī)模較小的相同問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。
3) 利用該問題分解出的子問題的解可以合并為該問題的解；
4) 該問題所分解出的各個(gè)子問題是相互獨(dú)立的，即子問題之間不包含公共的子子問題。

第一條特征是絕大多數(shù)問題都可以滿足的，因?yàn)閱栴}的計(jì)算復(fù)雜性一般是隨著問題規(guī)模的增加而增加；

第二條特征是應(yīng)用分治法的前提它也是大多數(shù)問題可以滿足的，此特征反映了遞歸思想的應(yīng)用；

第三條特征是關(guān)鍵，能否利用分治法完全取決于問題是否具有第三條特征，如果具備了第一條和第二條特征，而不具備第三條特征，則可以考慮用貪心法或動態(tài)規(guī)劃法。

第四條特征涉及到分治法的效率，如果各子問題是不獨(dú)立的則分治法要做許多不必要的工作，重復(fù)地解公共的子問題，此時(shí)雖然可用分治法，但一般用動態(tài)規(guī)劃法較好。

題目1. 給定一個(gè)順序表，編寫一個(gè)求出其最大值的分治算法。

# 基本子算法（子問題規(guī)模小于等于 2 時(shí)）def get_max(max_list):  return max(max_list) # 這里偷個(gè)懶！# 分治法 版本一def solve(init_list):  n = len(init_list)  if n <= 2: # 若問題規(guī)模小于等于 2，最終解決    return get_max(init_list)  # 分解（子問題規(guī)模為 2，最后一個(gè)可能為 1）  temp_list=(init_list[i:i+2] for i in range(0, n, 2))  # 分治，合并  max_list = list(map(get_max, temp_list))  # 遞歸（樹）  solve(max_list)# 分治法 版本二def solve2(init_list):  n = len(init_list)  if n <= 2: # 若問題規(guī)模小于等于 2，解決    return get_max(init_list)  # 分解（子問題規(guī)模為 n/2）  left_list, right_list = init_list[:n//2], init_list[n//2:]  # 遞歸（樹），分治  left_max, right_max = solve2(left_list), solve2(right_list)  # 合并  return get_max([left_max, right_max])if __name__ == "__main__":  # 測試數(shù)據(jù)  test_list = [12,2,23,45,67,3,2,4,45,63,24,23]  # 求最大值  print(solve(test_list)) # 67  print(solve2(test_list)) # 67

題目2. 給定一個(gè)順序表，判斷某個(gè)元素是否在其中。

# 子問題算法（子問題規(guī)模為 1）def is_in_list(init_list, el):  return [False, True][init_list[0] == el]# 分治法def solve(init_list, el):  n = len(init_list)  if n == 1: # 若問題規(guī)模等于 1，直接解決    return is_in_list(init_list, el)  # 分解（子問題規(guī)模為 n/2）  left_list, right_list = init_list[:n//2], init_list[n//2:]  # 遞歸（樹），分治，合并  res = solve(left_list, el) or solve(right_list, el)  return resif __name__ == "__main__":  # 測試數(shù)據(jù)  test_list = [12,2,23,45,67,3,2,4,45,63,24,23]  # 查找  print(solve2(test_list, 45)) # True  print(solve2(test_list, 5)) # False