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

分治法

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

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

基本步驟：

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

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

   第三步：直接求解，并返回問(wèn)題的解。

例3-7：識(shí)別假幣問(wèn)題。一個(gè)袋子里裝有偶數(shù)枚硬幣，其中有一枚為假幣，而且假幣的重量比真幣的輕。假幣和真幣從外形看一模一樣，無(wú)法分辨出來(lái)。請(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)行歸并排序的示例圖