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所示。