Python分治法定义与应用实例详解

# 基本子算法（子问题规模小于等于 2 时）
def get_max(max_list):
  return max(max_list) # 这里偷个懒！
# 分治法 版本一
def solve(init_list):
  n = len(init_list)
  if n <= 2: # 若问题规模小于等于 2，最终解决
    return get_max(init_list)
  # 分解（子问题规模为 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: # 若问题规模小于等于 2，解决
    return get_max(init_list)
  # 分解（子问题规模为 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__":
  # 测试数据
  test_list = [12,2,23,45,67,3,4,63,24,23]
  # 求最大值
  print(solve(test_list)) # 67
  print(solve2(test_list)) # 67

# 子问题算法（子问题规模为 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: # 若问题规模等于 1，直接解决
    return is_in_list(init_list,el)
  # 分解（子问题规模为 n/2）
  left_list,init_list[n//2:]
  # 递归（树），分治，合并
  res = solve(left_list,el) or solve(right_list,el)
  return res
if __name__ == "__main__":
  # 测试数据
  test_list = [12,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,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,1,6,7,9,13,93,100,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,hi
# 快速排序
def quicksort(seq):
  # 若问题规模小于等于1，解决
  if len(seq) <= 1: return seq
  # 分解
  lo,hi = partition(seq)
  # 递归（树），分治，合并
  return quicksort(lo) + [pi] + quicksort(hi)
seq = [7,5,8,2]
print(quicksort(seq)) #[0,9]

# 合并排序
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,2]
print(mergesort(seq)) #[0,9]

# 汉诺塔
def move(n,a,buffer,c):
  if n == 1:
    print(a,"->",c)
    #return
  else:
    # 递归（线性）
    move(n-1,c,buffer)
    move(1,c) # 或者：print(a,c)
    move(n-1,c)
move(3,"a","b","c")

# 爬楼梯
def climb(n=7):
  if n <= 2:
    return n
  return climb(n-1) + climb(n-2) # 等价于斐波那契数列！
print(climb(5)) # 8
print(climb(7)) # 21

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 # 若问题规模等于 2，直接解决
  # 分解（子问题规模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]  # 左侧最近点对
  rmin = (right,nearest_dot(right))[len(right) > 2] # 右侧最近点对
  # 合并
  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)  # 最近点对距离
  # 处理中线附近的带状区域（近似蛮力）
  left = list(filter(lambda p:mid_x - p[0] <= d,left))  #中间线左侧的距离<=d的点
  right = list(filter(lambda p:p[0] - mid_x <= d,right)) #中间线右侧的距离<=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:   #如果右侧部分点在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,(2,(6,(7,(8,5),(9,0),4)]
print(solve(seq)) # [(6,2)]
#print(divide_conquer(seq)) # [(6,2)]

'''
求一个算法：N个数，用其中M个任意组合相加等于一个已知数X。得出这M个数是哪些数。
比如：
seq = [1,9]
s = 14 # 和
全部可能的数字组合有：
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种
'''
# 版本一（纯计数）
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,9]
s = 14 # 和
print(find(seq,s)) # 15
seq = [11,31,15,20,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:],tmp)               # 尾递归 ---不含 seq[0] 的情况
  find2(seq[1:],s-seq[0],str(seq[0]) + '+' + tmp)  # 尾递归 ---含 seq[0] 的情况
# 测试
seq = [1,9]
s = 14 # 和
find2(seq,s)
print()
seq = [11,14]
s = 40 # 和
find2(seq,s)