欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Python分治法定義與應(yīng)用實例詳解

 更新時間:2017年07月28日 08:56:49   作者:羅兵  
這篇文章主要介紹了Python分治法定義與應(yīng)用,較為詳細的分析了Python分治法的概念、原理、用途,并結(jié)合實例總結(jié)了Python分治法的各種常見應(yīng)用,需要的朋友可以參考下

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

分治法所能解決的問題一般具有以下幾個特征:

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

第一條特征是絕大多數(shù)問題都可以滿足的,因為問題的計算復(fù)雜性一般是隨著問題規(guī)模的增加而增加;

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

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

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

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

# 基本子算法(子問題規(guī)模小于等于 2 時)
def get_max(max_list):
  return max(max_list) # 這里偷個懶!
# 分治法 版本一
def solve(init_list):
  n = len(init_list)
  if n <= 2: # 若問題規(guī)模小于等于 2,最終解決
    return get_max(init_list)
  # 分解(子問題規(guī)模為 2,最后一個可能為 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. 給定一個順序表,判斷某個元素是否在其中。

# 子問題算法(子問題規(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 res
if __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

題目3. 找出一組序列中的第 k 小的元素,要求線性時間

# 劃分(基于主元 pivot),注意:非就地劃分
def partition(seq):
  pi = seq[0]              # 挑選主元
  lo = [x for x in seq[1:] if x <= pi] # 所有小的元素
  hi = [x for x in seq[1:] if x > pi]  # 所有大的元素
  return lo, pi, hi
# 查找第 k 小的元素
def select(seq, k):
  # 分解
  lo, pi, hi = partition(seq)
  m = len(lo)
  if m == k:
    return pi        # 解決!
  elif m < k:
    return select(hi, k-m-1) # 遞歸(樹),分治
  else:
    return select(lo, k)   # 遞歸(樹),分治
if __name__ == '__main__':
  seq = [3, 4, 1, 6, 3, 7, 9, 13, 93, 0, 100, 1, 2, 2, 3, 3, 2]
  print(select(seq, 3)) #2
  print(select(seq, 5)) #2

題目4. 快速排序

# 劃分(基于主元 pivot),注意:非就地劃分
def partition(seq):
  pi = seq[0]              # 挑選主元
  lo = [x for x in seq[1:] if x <= pi] # 所有小的元素
  hi = [x for x in seq[1:] if x > pi]  # 所有大的元素
  return lo, pi, hi
# 快速排序
def quicksort(seq):
  # 若問題規(guī)模小于等于1,解決
  if len(seq) <= 1: return seq
  # 分解
  lo, pi, hi = partition(seq)
  # 遞歸(樹),分治,合并
  return quicksort(lo) + [pi] + quicksort(hi)
seq = [7, 5, 0, 6, 3, 4, 1, 9, 8, 2]
print(quicksort(seq)) #[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

題目5. 合并排序(二分排序)

# 合并排序
def mergesort(seq):
  # 分解(基于中點)
  mid = len(seq) // 2
  left_seq, right_seq = seq[:mid], seq[mid:]
  # 遞歸(樹),分治
  if len(left_seq) > 1: left_seq = mergesort(left_seq)
  if len(right_seq) > 1: right_seq = mergesort(right_seq)
  # 合并
  res = []
  while left_seq and right_seq:     # 只要兩者皆非空
    if left_seq[-1] >= right_seq[-1]: # 兩者尾部較大者,彈出
      res.append(left_seq.pop())
    else:
      res.append(right_seq.pop())
  res.reverse()             # 倒序
  return (left_seq or right_seq) + res  # 前面加上剩下的非空的seq
seq = [7, 5, 0, 6, 3, 4, 1, 9, 8, 2]
print(mergesort(seq)) #[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

題目6. 漢諾塔

# 漢諾塔
def move(n, a, buffer, c):
  if n == 1:
    print(a,"->",c)
    #return
  else:
    # 遞歸(線性)
    move(n-1, a, c, buffer)
    move(1, a, buffer, c) # 或者:print(a,"->",c)
    move(n-1, buffer, a, c)
move(3, "a", "b", "c")

問題7. 爬樓梯

假設(shè)你正在爬樓梯,需要n步你才能到達頂部。但每次你只能爬一步或者兩步,你能有多少種不同的方法爬到樓頂部?

# 爬樓梯
def climb(n=7):
  if n <= 2:
    return n
  return climb(n-1) + climb(n-2) # 等價于斐波那契數(shù)列!
print(climb(5)) # 8
print(climb(7)) # 21

問題8. 給定平面上n個點,找其中的一對點,使得在n個點的所有點對中,該點對的距離最小。(最近點對問題)

from math import sqrt
# 蠻力法
def solve(points):
  n = len(points)
  min_d = float("inf") # 最小距離:無窮大
  min_ps = None    # 最近點對
  for i in range(n-1):
    for j in range(i+1, n):
      d = sqrt((points[i][0] - points[j][0])**2 + (points[i][1] - points[j][1])**2) # 兩點距離
      if d < min_d:
        min_d = d            # 修改最小距離
        min_ps = [points[i], points[j]] # 保存最近點對
  return min_ps
# 最接近點對(報錯?。?
def nearest_dot(seq):
  # 注意:seq事先已對x坐標排序
  n = len(seq)
  if n <= 2: return seq # 若問題規(guī)模等于 2,直接解決
  # 分解(子問題規(guī)模n/2)
  left, right = seq[0:n//2], seq[n//2:]
  print(left, right)
  mid_x = (left[-1][0] + right[0][0])/2.0
  # 遞歸,分治
  lmin = (left, nearest_dot(left))[len(left) > 2]  # 左側(cè)最近點對
  rmin = (right, nearest_dot(right))[len(right) > 2] # 右側(cè)最近點對
  # 合并
  dis_l = (float("inf"), get_distance(lmin))[len(lmin) > 1]
  dis_r = (float("inf"), get_distance(rmin))[len(rmin) > 1]
  d = min(dis_l, dis_r)  # 最近點對距離
  # 處理中線附近的帶狀區(qū)域(近似蠻力)
  left = list(filter(lambda p:mid_x - p[0] <= d, left))  #中間線左側(cè)的距離<=d的點
  right = list(filter(lambda p:p[0] - mid_x <= d, right)) #中間線右側(cè)的距離<=d的點
  mid_min = []
  for p in left:
    for q in right:
      if abs(p[0]-q[0])<=d and abs(p[1]-q[1]) <= d:   #如果右側(cè)部分點在p點的(d,2d)之間
        td = get_distance((p,q))
        if td <= d:
          mid_min = [p,q]  # 記錄p,q點對
          d = td      # 修改最小距離
  if mid_min:
    return mid_min
  elif dis_l>dis_r:
    return rmin
  else:
    return lmin
# 兩點距離
def get_distance(min):
  return sqrt((min[0][0]-min[1][0])**2 + (min[0][1]-min[1][1])**2)
def divide_conquer(seq):
  seq.sort(key=lambda x:x[0])
  res = nearest_dot(seq)
  return res
# 測試
seq=[(0,1),(3,2),(4,3),(5,1),(1,2),(2,1),(6,2),(7,2),(8,3),(4,5),(9,0),(6,4)]
print(solve(seq)) # [(6, 2), (7, 2)]
#print(divide_conquer(seq)) # [(6, 2), (7, 2)]

問題9. 從數(shù)組 seq 中找出和為 s 的數(shù)值組合,有多少種可能

'''
求一個算法:N個數(shù),用其中M個任意組合相加等于一個已知數(shù)X。得出這M個數(shù)是哪些數(shù)。
比如:
seq = [1, 2, 3, 4, 5, 6, 7, 8, 9]
s = 14 # 和
全部可能的數(shù)字組合有:
5+9, 6+8
1+4+9, 1+5+8, 1+6+7, 2+3+9, 2+4+8, 2+5+7, 3+4+7, 3+5+6
1+2+5+6, 1+3+4+6, 1+2+4+7, 1+2+3+8, 2+3+4+5
共計15種
'''
# 版本一(純計數(shù))
def find(seq, s):
  n = len(seq)
  if n==1:
    return [0, 1][seq[0]==s]
  if seq[0]==s:
    return 1 + find(seq[1:], s)
  else:
    return find(seq[1:], s-seq[0]) + find(seq[1:], s)
# 測試
seq = [1, 2, 3, 4, 5, 6, 7, 8, 9]
s = 14 # 和
print(find(seq, s)) # 15
seq = [11,23,6,31,8,9,15,20,24,14]
s = 40 # 和
print(find(seq, s)) #8
# 版本二 (打印)
def find2(seq, s, tmp=''):
  if len(seq)==0:  # 終止條件
    return
  if seq[0] == s:        # 找到一種,則
    print(tmp + str(seq[0])) # 打印
  find2(seq[1:], s, tmp)               # 尾遞歸 ---不含 seq[0] 的情況
  find2(seq[1:], s-seq[0], str(seq[0]) + '+' + tmp)  # 尾遞歸 ---含 seq[0] 的情況
# 測試
seq = [1, 2, 3, 4, 5, 6, 7, 8, 9]
s = 14 # 和
find2(seq, s)
print()
seq = [11,23,6,31,8,9,15,20,24,14]
s = 40 # 和
find2(seq, s)

更多關(guān)于Python相關(guān)內(nèi)容可查看本站專題:《Python數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Python Socket編程技巧總結(jié)》、《Python函數(shù)使用技巧總結(jié)》、《Python字符串操作技巧匯總》、《Python入門與進階經(jīng)典教程》及《Python文件與目錄操作技巧匯總

希望本文所述對大家Python程序設(shè)計有所幫助。

相關(guān)文章

  • python獲取當前計算機cpu數(shù)量的方法

    python獲取當前計算機cpu數(shù)量的方法

    這篇文章主要介紹了python獲取當前計算機cpu數(shù)量的方法,涉及Python操作計算機硬件的技巧,代碼簡單易懂,非常具有實用價值,需要的朋友可以參考下
    2015-04-04
  • tensorflow輸出權(quán)重值和偏差的方法

    tensorflow輸出權(quán)重值和偏差的方法

    本篇文章主要介紹了tensorflow輸出權(quán)重值和偏差的方法,小編覺得挺不錯的,現(xiàn)在分享給大家,也給大家做個參考。一起跟隨小編過來看看吧
    2018-02-02
  • 深入探究Flask的兩個高級特性之藍圖和JWT認證

    深入探究Flask的兩個高級特性之藍圖和JWT認證

    本文將探討 Flask 的兩個高級特性:藍圖(Blueprints)和 JSON Web Token(JWT)認證,藍圖讓我們可以將應(yīng)用模塊化,以便更好地組織代碼;而 JWT 認證是現(xiàn)代 Web 應(yīng)用中常見的一種安全機制,感興趣的小伙伴跟著小編一起來看看吧
    2023-08-08
  • 解決pycharm安裝后代碼區(qū)不能編輯的問題

    解決pycharm安裝后代碼區(qū)不能編輯的問題

    今天小編就為大家分享一篇解決pycharm安裝后代碼區(qū)不能編輯的問題,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2018-10-10
  • python下10個簡單實例代碼

    python下10個簡單實例代碼

    最近學(xué)python比較順手,找到感覺了,所以,我想把我用來練習(xí)的實例題目分享出來,有興趣的朋友可以關(guān)注一下。 文章分為10篇,每篇10題,共100道實例。后續(xù)如果需要可以增加
    2017-11-11
  • 解決python運行啟動報錯問題

    解決python運行啟動報錯問題

    這篇文章主要介紹了解決python運行啟動報錯問題,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2020-06-06
  • 教你利用python實現(xiàn)企業(yè)微信發(fā)送消息

    教你利用python實現(xiàn)企業(yè)微信發(fā)送消息

    今天帶大家來練習(xí)python實戰(zhàn),文中對利用python實現(xiàn)企業(yè)微信發(fā)送消息作了詳細的圖文解說及代碼示例,對正在學(xué)習(xí)python的小伙伴很有幫助,需要的朋友可以參考下
    2021-05-05
  • 基于windows下pip安裝python模塊時報錯總結(jié)

    基于windows下pip安裝python模塊時報錯總結(jié)

    今天小編就為大家分享一篇基于windows下pip安裝python模塊時報錯總結(jié),具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2018-06-06
  • Django ORM 查詢管理器源碼解析

    Django ORM 查詢管理器源碼解析

    這篇文章主要介紹了Django ORM 查詢管理器源碼解析,文中通過示例代碼介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下
    2019-08-08
  • Python中__init__.py文件的作用

    Python中__init__.py文件的作用

    這篇文章主要介紹了Python中__init__.py文件的作用,在PyCharm中,帶有__init__.py這個文件的目錄被認為是Python的包目錄,與普通目錄的圖標有不一樣的顯示
    2022-09-09

最新評論