計(jì)算機(jī)算法設(shè)計(jì)的基本方法（4）

分治法

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

思想：常常要借助遞歸的結(jié)構(gòu)，逐層求解，當(dāng)問題規(guī)模達(dá)到某個(gè)簡(jiǎn)單情況時(shí)，解容易直接得出，而不必繼續(xù)分解。

基本步驟：

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

   第二步：將問題劃分為多個(gè)子問題，并分別遞歸調(diào)用分治法過程，求出多個(gè)解，并將多個(gè)子問題的解進(jìn)行合并。

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

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

分析：

例3-8：歸并排序。

某數(shù)列存儲(chǔ)在序列A[1]，A[2]，……，A[n]，現(xiàn)采用歸并思想進(jìn)行排序。

分析：

例3-8的N-S圖

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