計算機算法設計的基本方法（4）

分治法

定義：將問題分而治之，把一個復雜的問題分成兩個或更多的相同或相似的子問題，再把子問題分成更小的子問題，直到最后的子問題可以簡單的直接求解，原問題的解為子問題解的合并。

思想：常常要借助遞歸的結構，逐層求解，當問題規模達到某個簡單情況時，解容易直接得出，而不必繼續分解。

基本步驟：

   第一步：判斷問題是否可分。如果可分，轉第二步；否則轉第三步。

   第二步：將問題劃分為多個子問題，并分別遞歸調用分治法過程，求出多個解，并將多個子問題的解進行合并。

   第三步：直接求解，并返回問題的解。

例3-7：識別假幣問題。一個袋子里裝有偶數枚硬幣，其中有一枚為假幣，而且假幣的重量比真幣的輕。假幣和真幣從外形看一模一樣，無法分辨出來。請從中找出這枚假幣。

分析：

例3-8：歸并排序。

某數列存儲在序列A[1]，A[2]，……，A[n]，現采用歸并思想進行排序。

分析：

例3-8的N-S圖

序列（5，3，4，2，1，3，6，2）進行歸并排序的示例圖