3.5　分治算法思想

分治算法是一種化繁為簡的算法思想。分治算法往往應用于計算步驟比較復雜的問題，通過將問題簡化而逐步得到結果。

3.5.1　分治算法基本思想

分治算法的基本思想是將一個計算復雜的問題分為規模較小、計算簡單的小問題求解，然后綜合各個小問題，得到最終問題的答案。分治算法的執行過程如下：

（1）對于一個規模為N的問題，若該問題比較容易解決（比如規模N較小），則直接解決；否則執行下面的步驟。

（2）將該問題分解為M個規模較小的子問題，這些子問題互相獨立，并且與原問題形式相同。

（3）遞歸地解這些子問題。

（4）然后，將各子問題的解合并得到原問題的解。

使用分治算法需要待求解問題能夠轉化為若干個小規模的相同問題，通過逐步劃分，能夠達到一個易于求解的階段而直接進行求解。然后，程序中可以使用遞歸算法來進行求解。

3.5.2　分治算法實例

下面通過一個例子來分析分治算法的應用。一個袋子里有30個硬幣，其中一枚是假幣，并且假幣和真幣一模一樣，肉眼很難分辨，目前只知道假幣比真幣的重量輕一點。請問，如何區分出假幣呢？

1.分治算法

先來分析一下尋找假幣問題。可以采用遞歸分治的思想來求解這個問題，操作步驟如下：

（1）首先為每個硬幣編號，然后將所有的硬幣等分為兩份，放在天平的兩邊。這樣就將區分30個硬幣的問題，變為區別兩堆硬幣的問題。

（2）因為假幣的重量較輕，因此天平較輕的一側中一定包含假幣。

（3）再將較輕的一側中的硬幣等分為兩份，重復上述做法。

（4）直到剩下兩枚硬幣，可用天平直接找出假幣。

這種方法在硬幣個數比較多的時候便顯示出了優勢。可以按照這個思路來編寫相應的尋找假幣問題的求解算法，代碼示例如下：

在上述代碼中，輸入參數coin為硬幣重量數組，輸入參數low為尋找的起始硬幣編號，輸入參數high為尋找的結束硬幣編號。該方法的返回值便是假幣的位置，即假幣的編號。程序中嚴格遵循了前面的分治遞歸算法，讀者可以對照著加深理解。

2.分治算法尋找假幣

學習了上述通用的分治算法尋找假幣問題算法后，下面給出完整的尋找假幣問題的程序代碼：

【程序3-4】

在該程序中，主方法首先由用戶輸入硬幣總的個數，然后由用戶輸入硬幣的真假，最后調用FalseCoin（）方法進行求解。這里，用戶輸入的硬幣真假數組用重量來表示，例如，以2表示真幣的重量，以1表示假幣的重量。

該程序的執行結果，如圖3-4所示。