设计思想之分治

什么是分治

分治法的思想是分而治之,就是把一个复杂问题分成两个或更多相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,将最后子问题的解合并得到原问题的解。因为问题小到一定规模可以更好解决,将一个问题分解若干个相同问题,再利用分解出若干子问题的解可以合并为该问题的解。这个技巧是很多高效算法的基础。

应用分治的示例

找出列表中最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def max_num(lst):
return max(lst)

def solve(lst):
n = len(lst)
# 分治
# 长度小于等于2,取最大
if n <= 2:
return max_num(lst)
# 分解
left, right = lst[:n//2], lst[n//2:]
# 递归 分治
left_max,right_max = solve(left),solve(right)
return max_num([left_max,right_max])

lst = [5,6,3,1,9,4,0,8,7,2]
print(solve(lst))

给定一个列表,判断某个元素是否在其中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def in_lst(lst,key):
if lst[0] == key:
return True
else:
return False

def solve(lst, key):
n = len(lst)
# 当列表长度为1情况
if n == 1:
return in_lst(lst,key)
# 分解
left, right = lst[:n//2], lst[n//2:]
result = solve(left,key) or solve(right,key)
if result:
return "OK"
return None

lst = [5,6,3,1,9,4,0,8,7,2]
key = 10
print(solve(lst,key))
0%