1 概念

??分治算法，根據(jù)字面意思解釋是“分而治之”，就是把一個(gè)復(fù)雜的問(wèn)題分成兩個(gè)或更多的相同或相似的子問(wèn)題，再把子問(wèn)題分成更小的子問(wèn)題……直到最后子問(wèn)題可以簡(jiǎn)單的直接求解，原問(wèn)題的解即子問(wèn)題的解的合并。

2 算法策略

??分治策略：對(duì)于一個(gè)規(guī)模為 n 的問(wèn)題，若該問(wèn)題可以容易地解決（比如說(shuō)規(guī)模 n 較?。﹦t直接解決，否則將其分解為 k 個(gè)規(guī)模較小的子問(wèn)題，這些子問(wèn)題互相獨(dú)立且與原問(wèn)題形式相同，遞歸地解這些子問(wèn)題，然后將各子問(wèn)題的解合并得到原問(wèn)題的解。
??在平時(shí)日常生活中，分治思想也是隨處可見(jiàn)的。例如：當(dāng)我們打牌時(shí)，在進(jìn)行洗牌時(shí)，若牌的數(shù)目較多，一個(gè)人洗不過(guò)來(lái)，則會(huì)將牌進(jìn)行分堆，單獨(dú)洗一小堆牌是相對(duì)容易的，每一堆牌都洗完之后再放到一起，則完成洗牌過(guò)程。

3 使用場(chǎng)景

??（1）該問(wèn)題的規(guī)?？s小到一定的程度就可以容易地解決。
??（2）該問(wèn)題可以分解為若干個(gè)規(guī)模較小的相同問(wèn)題，即該問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。
??（3）利用該問(wèn)題分解出的子問(wèn)題的解可以合并為該問(wèn)題的解。
??（4）該問(wèn)題所分解出的各個(gè)子問(wèn)題是相互獨(dú)立的，即子問(wèn)題之間不包含公共的子問(wèn)題。

4 基本步驟

分治法在每一層遞歸上都有三個(gè)步驟：
??（1）分解：將原問(wèn)題分解為若干個(gè)規(guī)模較小，相互獨(dú)立，與原問(wèn)題形式相同的子問(wèn)題。
??（2）求解：若子問(wèn)題規(guī)模較小而容易被解決則直接解，否則遞歸地解各個(gè)子問(wèn)題。
??（3）合并：將各個(gè)子問(wèn)題的解合并為原問(wèn)題的解。

5 偽代碼

??其中，|P| 表示問(wèn)題 P 的規(guī)模，n0 為一閾值，表示當(dāng)問(wèn)題 P 的規(guī)模不超過(guò) n0 時(shí)，問(wèn)題已容易直接解出，不必再繼續(xù)分解。ADHOC(P) 是該分治法中的基本子算法，用于直接解小規(guī)模的問(wèn)題 P。因此，當(dāng) P 的規(guī)模不超過(guò)n0 時(shí)直接用算法 ADHOC(P) 求解。算法 MERGE(y1,y2,…,yk) 是該分治法中的合并子算法，用于將 P 的子問(wèn)題 P1 ,P2 ,…,Pk 的相應(yīng)的解 y1 , y2 ,…, yk 合并為 P 的解。

6 典型案例

6.1 二分查找

??二分查找是典型的分治算法的應(yīng)用。需要注意的是，二分查找的前提是查找的數(shù)列是有序的。

算法流程：
??（1）選擇一個(gè)標(biāo)志 i 將集合分為二個(gè)子集合。
??（2）判斷標(biāo)志 L(i) 是否能與要查找的值 des 相等，相等則直接返回。
??（3）否則判斷 L(i) 與 des 的大小。
??（4）基于判斷的結(jié)果決定下步是向左查找還是向右查找。
??（5）遞歸繼續(xù)上面的步驟。

??通過(guò)二分查找的流程可以看出，二分查找是將原有序數(shù)列劃分為左右兩個(gè)子序列，然后在對(duì)兩個(gè)子序列中的其中一個(gè)在進(jìn)行劃分，直至查找成功。

代碼實(shí)現(xiàn)：

#include<string.h>
#include<stdio.h>
int k;
int binarysearch(int a[],int x,int low,int high)//a表示需要二分的有序數(shù)組（升序），x表示需要查找的數(shù)字，low，high表示高低位
{
    if(low>high)
    {
        return -1;//沒(méi)有找到
    }
    int mid=(low+high)/2;
    if(x==a[mid])//找到x
    {
        k=mid;
        return x;
    }
    else if(x>a[mid]) //x在后半部分
    {
        binarysearch(a,x,mid+1,high);//在后半部分繼續(xù)二分查找
    }
    else//x在前半部分
    {
        binarysearch(a,x,low,mid-1);
    }
}

int main()
{
    int a[10]={1,2,3,4,5,6,7,8,9,10};
    printf('請(qǐng)輸入需要查找的正數(shù)字：\n');
    int x;
    scanf('%d',&x);
    int r=binarysearch(a,x,0,9);
    if(r==-1)
    {
        printf('沒(méi)有查到\n');
    }
    else
    {
        printf('查到了,在數(shù)列的第%d個(gè)位置上\n',k+1);
    }
    return 0;
}

6.2 全排列問(wèn)題

問(wèn)題描述：
??有1，2，3，4個(gè)數(shù)，問(wèn)你有多少種排列方法，并輸出排列。
問(wèn)題分析：
??若采用分治思想進(jìn)行求解，首先需要把大問(wèn)題分解成很多的子問(wèn)題，大問(wèn)題是所有的排列方法。那么我們分解得到的小問(wèn)題就是以 1 開(kāi)頭的排列，以 2 開(kāi)頭的排列，以 3 開(kāi)頭的排列，以 4 開(kāi)頭的排列?，F(xiàn)在這些問(wèn)題有能繼續(xù)分解，比如以 1 開(kāi)頭的排列中，只確定了 1 的位置，沒(méi)有確定 2 ，3 ，4 的位置，把 2，3，4 三個(gè)又看成大問(wèn)題繼續(xù)分解，2 做第二個(gè)，3 做第二個(gè)，或者 4 做第二個(gè)。一直分解下去，直到分解成的子問(wèn)題只有一個(gè)數(shù)字的時(shí)候，不能再分解。只有一個(gè)數(shù)的序列只有一種排列方式，則子問(wèn)題求解容易的多。
代碼實(shí)現(xiàn)：

6.3 歸并排序

??歸并排序：歸并（Merge）排序法是將兩個(gè)（或兩個(gè)以上）有序表合并成一個(gè)新的有序表，即把待排序序列分為若干個(gè)子序列，每個(gè)子序列是有序的。然后再把有序子序列合并為整體有序序列。即先劃分為兩個(gè)部分，最后進(jìn)行合并。

歸并排序

偽代碼：

算法 MergeSort(A, p, r)
輸入：數(shù)組A[p...r]
輸出：有序數(shù)組A
if(p < r)
    then q <- (p+r)/2//折半劃分
        MergeSort(A, p ,q)//子問(wèn)題1
        MergeSort(A, p ,q)//子問(wèn)題2
        Merge(A, p ,q, r)//合并求解

代碼實(shí)現(xiàn)：

6.4 快速排序

??快速排序的基本思想：當(dāng)前待排序的無(wú)序區(qū)為 A[low..high] ，利用分治法可將快速排序的基本思想描述為：
（1）分解：
??在A[low..high]中任選一個(gè)記錄作為基準(zhǔn)(pivot)，以此基準(zhǔn)將當(dāng)前無(wú)序區(qū)劃分為左、右兩個(gè)較小的子區(qū)間R[low..pivotpos-1) 和 R[pivotpos+1..high] ，并使左邊子區(qū)間中所有記錄的關(guān)鍵字均小于等于基準(zhǔn)記錄(不妨記為pivot)的關(guān)鍵字 pivot.key，右邊的子區(qū)間中所有記錄的關(guān)鍵字均大于等于pivot.key，而基準(zhǔn)記錄pivot則位于正確的位置( pivotpos )上，它無(wú)須參加后續(xù)的排序。

（2）求解：
??通過(guò)遞歸調(diào)用快速排序?qū)ψ?、右子區(qū)間R[low..pivotpos-1]和R[pivotpos+1..high]快速排序。
（3）合并：
??因?yàn)楫?dāng)'求解'步驟中的兩個(gè)遞歸調(diào)用結(jié)束時(shí)，其左、右兩個(gè)子區(qū)間已有序。對(duì)快速排序而言，'組合'步驟無(wú)須做什么，可看作是空操作。

快速排序

代碼實(shí)現(xiàn)：

#include <iostream>
using namespace std;
void QuickSort(int arr[], int low, int high){
    if (high <= low) return;
    int i = low;
    int j = high + 1;
    int key = arr[low];
    while (true)
    {
        /*從左向右找比key大的值*/
        while (arr[++i] < key)
        {
            if (i == high){
                break;
            }
        }
        /*從右向左找比key小的值*/
        while (arr[--j] > key)
        {
            if (j == low){
                break;
            }
        }
        if (i >= j) break;
        /*交換i,j對(duì)應(yīng)的值*/
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    /*中樞值與j對(duì)應(yīng)值交換*/
    int temp = arr[low];
    arr[low] = arr[j];
    arr[j] = temp;
    QuickSort(arr, low, j - 1);
    QuickSort(arr, j + 1, high);
}

6.5 漢諾塔

漢諾塔（Hanoi Tower）問(wèn)題也是一個(gè)經(jīng)典的遞歸問(wèn)題，該問(wèn)題描述如下：

漢諾塔問(wèn)題：古代有一個(gè)梵塔，塔內(nèi)有三個(gè)座A、B、C，A座上有64個(gè)盤(pán)子，盤(pán)子大小不等，大的在下，小的在上。有一個(gè)和尚想把這個(gè)盤(pán)子從A座移到B座，但每次只能允許移動(dòng)一個(gè)盤(pán)子，并且在移動(dòng)過(guò)程中，3個(gè)座上的盤(pán)子始終保持大盤(pán)在下，小盤(pán)在上。

• ①  如果只有 1 個(gè)盤(pán)子，則不需要利用 B 塔，直接將盤(pán)子從 A 移動(dòng)到 C 。

• ② 如果有 2 個(gè)盤(pán)子，可以先將盤(pán)子 2 上的盤(pán)子 1 移動(dòng)到 B ；將盤(pán)子 2 移動(dòng)到 C ；將盤(pán)子 1 移動(dòng)到 C 。這說(shuō)明了：可以借助 B 將 2 個(gè)盤(pán)子從 A 移動(dòng)到 C ，當(dāng)然，也可以借助 C 將 2 個(gè)盤(pán)子從 A 移動(dòng)到 B 。

• ③ 如果有 3 個(gè)盤(pán)子，那么根據(jù) 2 個(gè)盤(pán)子的結(jié)論，可以借助 C 將盤(pán)子 3 上的兩個(gè)盤(pán)子從 A 移動(dòng)到 B ；將盤(pán)子 3 從 A 移動(dòng)到 C ，A 變成空座；借助 A 座，將 B 上的兩個(gè)盤(pán)子移動(dòng)到 C 。

• ④ 以此類推，上述的思路可以一直擴(kuò)展到 n 個(gè)盤(pán)子的情況，將將較小的 n-1個(gè)盤(pán)子看做一個(gè)整體，也就是我們要求的子問(wèn)題，以借助 B 塔為例，可以借助空塔 B 將盤(pán)子A上面的 n-1 個(gè)盤(pán)子從 A 移動(dòng)到 B ；將A 最大的盤(pán)子移動(dòng)到 C ， A 變成空塔；借助空塔 A ，將 B 塔上的 n-2 個(gè)盤(pán)子移動(dòng)到 A，將 C 最大的盤(pán)子移動(dòng)到 C， B 變成空塔。。。

代碼實(shí)現(xiàn)：

7 總結(jié)分析

??分治法將規(guī)模為 n 的問(wèn)題分成 k 個(gè)規(guī)模為 n／m 的子問(wèn)題去解。設(shè)分解閥值 n0 = 1 ，且 adhoc 解規(guī)模為 1 的問(wèn)題耗費(fèi) 1 個(gè)單位時(shí)間。再設(shè)將原問(wèn)題分解為 k 個(gè)子問(wèn)題以及用 merge 將 k 個(gè)子問(wèn)題的解合并為原問(wèn)題的解需用 f(n) 個(gè)單位時(shí)間。用T(n)表示該分治法解規(guī)模為 |P| = n 的問(wèn)題所需的計(jì)算時(shí)間，則有：
??T（n）= k T(n/m) + f(n)