成人app

成人app        分治算法的基本思想是將一個規模為N的問題分解為K個規模較小的子問題，這些子問題相互獨立且與原問題性質相同。求出子問題的解，就可得到原問題的解，是一種分目標完成程序算法，簡單的問題可用二分法完成。

    1. 分治算法

成人app        我們在使用分治算法求解問題的時候是把一個問題劃分為多個小問題，然后通過各個小問題的答案來找到合適的，如果數據規模還是比較大，那么可以再進行一次分治算法，直到找到答案為止。

        分治算法的解題步驟一般如下：

        （1）分解，將要解決的問題劃分成若干規模較小的同類問題；

        （2）求解，當子問題劃分得足夠小時，用較簡單的方法解決；

        （3）合并，按原問題的要求，將子問題的解逐層合并構成原問題的解。

    2. 求n個元素中的最小值

成人app        一個列表中存在n個數據的時候，找到其中的最大值，當然這個問題我們使用Python可以直接通過max()函數和min()函數來解決，在這里我們使用分治算法來解決這個問題。

        問題分析，如果這個問題的數據規模小于等于2的時候，我們可以經過一個判斷就找到其中的最小值，所以我們需要做的就是想辦法把這若干個數據變成兩個數據進行比較，那么我們可以先把數據從中間劃分為左右兩部分，然后通過遞歸再把每一部分再劃分為左右兩部分，直到數據規模小于等于2的時候，返回結果，然后通過遞歸到最后為兩個數據對比，我們就可以找到最小值。

成人app        代碼如下：

def get_max(number):#尋最小值函數
    if len(number) == 1
        return number[0]
    else:
        if number[1]>number[0]:
            return number[0]
        else:
            return number[1]
# 分治法
def solve(number):
    n = len(number)
    if n <= 2:  # 數據規模小于等于2使用get_max()函數
        return get_max(number)
    # 分解（子問題規模為 n/2）
    left_list, right_list = number[:n // 2], number[n // 2:]
    # 遞歸（樹），分治
    left_max, right_max = solve(left_list), solve(right_list)
    # 合并
    return get_max([left_max, right_max])
if __name__ == "__main__":
    # 測試數據
    test_list = [33,52,2,25,63,75,43,72,45,97,53,25,14,18,3,5]
    # 求出最小值
    print(solve(test_list))

        輸出結果為：

  2

     3. 找到一組數據中第 k 小的元素

        代碼如下：

 def divide(number):# 劃分函數
    fis = number[0]#定義一個主元
    litter = [x for x in number[1:] if x < fis]#比主元小的元素存放一個列表
    big = [x for x in number[1:] if x >= fis]#比主元大的元素存放一個列表
    return fis,litter,big
def find(number,key):# 查找第 k 小的元素
    fis,litter,big = divide(number) #分解
    n = len(litter)
    if n == key:
        return fis#找到
    elif n < key:
        return find(big,key-n-1)#遞歸分治
    else:
        return find(litter,key)#遞歸分治
if __name__ == '__main__':
    list = [3, 45, 18, 65, 53,15,26,37, 27, 49, 17, 93, 0, 100, 13, 62, 52, 7, 24, 29]
    print('第5小的元素:',find(list,5))
    print('第10小的元素:',find(list,10))

成人app        輸出結果為：

第5小的元素: 17
第10小的元素: 29

     4. 總結

        關于分治算法，它的實質就是將每個子問題獨立，然后遞歸求解，來幫助我們解決數據規模較大的問題，它的缺點在于當子問題不獨立的時候就需要求公共子問題，所以我們在運用的時候一定要考慮一下是否適合分治算法。