分治算法思想

在編程過(guò)程中，經(jīng)常遇到處理數(shù)據(jù)相當(dāng)多、求解過(guò)程比較復(fù)雜、直接求解會(huì)比較耗時(shí)的問(wèn)題。在求解這類問(wèn)題時(shí)，可以采用各個(gè)擊破的方法。具體做法是：先把這個(gè)問(wèn)題分解成幾個(gè)較小的子問(wèn)題，找到求出這幾個(gè)子問(wèn)題的解法后，再找到合適的方法，把它們組合成求整個(gè)大問(wèn)題的解。如果這些子問(wèn)題還是比較大，可以繼續(xù)把它們分成幾個(gè)更小的子問(wèn)題，以此類推，直至可以直接求出解為止。

解題步驟

1. 分解，將要解決的問(wèn)題劃分成若干個(gè)規(guī)模較小的同類問(wèn)題。
2. 求解，當(dāng)子問(wèn)題劃分得足夠小時(shí)，用較簡(jiǎn)單的方法解決。
3. 合并，按原問(wèn)題的要求，將子問(wèn)題的解逐層合并構(gòu)成原問(wèn)題的解。

求順序表中最大值

# 返回兩個(gè)值中的最大值
def get_max(max_list):
    if len(max_list) > 1 and max_list[0] <= max_list[1]:
        return max_list[1]
    else:
        return max_list[0]

def solve(init_list):
    n = len(init_list)
    if n <= 2:
        return get_max(init_list)

    left_list, right_list = init_list[:n//2], init_list[n//2:]
    left_max, right_max = solve(left_list), solve(right_list)
    return get_max([left_max, right_max])

if __name__ == '__main__':
    test_list = [12, 2, 23, 45, 67, 3, 2, 4, 45, 63, 24, 23]
    print(solve(test_list))  # 67

判斷某個(gè)元素是否在列表中

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:
        return is_in_list(init_list, el)

    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__':
    test_list = [12, 2, 23, 45, 67, 3, 2, 4, 45, 63, 24, 23]
    print(solve(test_list, 45))  # True
    print(solve(test_list, 5))  # False

找出序列中第 k 小的元素

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 select(seq, k):
    lo, pi, hi = partition(seq)

    m = len(lo)
    if m == k - 1:
        return pi
    elif m < k - 1:
        return select(hi, k - 1 - m)
    else:
        return select(lo, k)

if __name__ == '__main__':
    test_list = [5, 2, 8, 7, 6, 3, 1, 4, 9, 10, 12, 11]
    print(select(test_list, 7))  # 7
    print(select(test_list, 3))  # 3