# 基本子算法（子問(wèn)題規(guī)模小于等于 2 時(shí)）def get_max(max_list):  return max(max_list) # 這里偷個(gè)懶！# 分治法 版本一def solve(init_list):  n = len(init_list)  if n <= 2: # 若問(wèn)題規(guī)模小于等于 2，最終解決    return get_max(init_list)  # 分解（子問(wèn)題規(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))  # 遞歸（樹(shù)）  solve(max_list)# 分治法 版本二def solve2(init_list):  n = len(init_list)  if n <= 2: # 若問(wèn)題規(guī)模小于等于 2，解決    return get_max(init_list)  # 分解（子問(wèn)題規(guī)模為 n/2）  left_list, right_list = init_list[:n//2], init_list[n//2:]  # 遞歸（樹(shù)），分治  left_max, right_max = solve2(left_list), solve2(right_list)  # 合并  return get_max([left_max, right_max])if __name__ == "__main__":  # 測(cè)試數(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

# 子問(wèn)題算法（子問(wèn)題規(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: # 若問(wèn)題規(guī)模等于 1，直接解決    return is_in_list(init_list, el)  # 分解（子問(wèn)題規(guī)模為 n/2）  left_list, right_list = init_list[:n//2], init_list[n//2:]  # 遞歸（樹(shù)），分治，合并  res = solve(left_list, el) or solve(right_list, el)  return resif __name__ == "__main__":  # 測(cè)試數(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

# 劃分（基于主元 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) # 遞歸（樹(shù)），分治  else:    return select(lo, k)   # 遞歸（樹(shù)），分治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

# 劃分（基于主元 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):  # 若問(wèn)題規(guī)模小于等于1，解決  if len(seq) <= 1: return seq  # 分解  lo, pi, hi = partition(seq)  # 遞歸（樹(shù)），分治，合并  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]

# 合并排序def mergesort(seq):  # 分解（基于中點(diǎn)）  mid = len(seq) // 2  left_seq, right_seq = seq[:mid], seq[mid:]  # 遞歸（樹(shù)），分治  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  # 前面加上剩下的非空的seqseq = [7, 5, 0, 6, 3, 4, 1, 9, 8, 2]print(mergesort(seq)) #[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

# 漢諾塔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")

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

from math import sqrt# 蠻力法def solve(points):  n = len(points)  min_d = float("inf") # 最小距離：無(wú)窮大  min_ps = None    # 最近點(diǎn)對(duì)  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) # 兩點(diǎn)距離      if d < min_d:        min_d = d            # 修改最小距離        min_ps = [points[i], points[j]] # 保存最近點(diǎn)對(duì)  return min_ps# 最接近點(diǎn)對(duì)（報(bào)錯(cuò)！）def nearest_dot(seq):  # 注意：seq事先已對(duì)x坐標(biāo)排序  n = len(seq)  if n <= 2: return seq # 若問(wèn)題規(guī)模等于 2，直接解決  # 分解（子問(wèn)題規(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è)最近點(diǎn)對(duì)  rmin = (right, nearest_dot(right))[len(right) > 2] # 右側(cè)最近點(diǎn)對(duì)  # 合并  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)  # 最近點(diǎn)對(duì)距離  # 處理中線附近的帶狀區(qū)域（近似蠻力）  left = list(filter(lambda p:mid_x - p[0] <= d, left))  #中間線左側(cè)的距離<=d的點(diǎn)  right = list(filter(lambda p:p[0] - mid_x <= d, right)) #中間線右側(cè)的距離<=d的點(diǎn)  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è)部分點(diǎn)在p點(diǎn)的(d,2d)之間        td = get_distance((p,q))        if td <= d:          mid_min = [p,q]  # 記錄p，q點(diǎn)對(duì)          d = td      # 修改最小距離  if mid_min:    return mid_min  elif dis_l>dis_r:    return rmin  else:    return lmin# 兩點(diǎn)距離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# 測(cè)試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)]

'''求一個(gè)算法：N個(gè)數(shù)，用其中M個(gè)任意組合相加等于一個(gè)已知數(shù)X。得出這M個(gè)數(shù)是哪些數(shù)。比如：seq = [1, 2, 3, 4, 5, 6, 7, 8, 9]s = 14 # 和全部可能的數(shù)字組合有：5+9, 6+81+4+9, 1+5+8, 1+6+7, 2+3+9, 2+4+8, 2+5+7, 3+4+7, 3+5+61+2+5+6, 1+3+4+6, 1+2+4+7, 1+2+3+8, 2+3+4+5共計(jì)15種'''# 版本一（純計(jì)數(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)# 測(cè)試seq = [1, 2, 3, 4, 5, 6, 7, 8, 9]s = 14 # 和print(find(seq, s)) # 15seq = [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] 的情況# 測(cè)試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)