计算机算法设计的基本方法（4）

计算机算法设计的基本方法（4）

分治法

定义：将问题分而治之，把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题，直到最后的子问题可以简单的直接求解，原问题的解为子问题解的合并。

思想：常常要借助递归的结构，逐层求解，当问题规模达到某个简单情况时，解容易直接得出，而不必继续分解。

基本步骤：

   第一步：判断问题是否可分。如果可分，转第二步；否则转第三步。

   第二步：将问题划分为多个子问题，并分别递归调用分治法过程，求出多个解，并将多个子问题的解进行合并。

   第三步：直接求解，并返回问题的解。

例3-7：识别假币问题。一个袋子里装有偶数枚硬币，其中有一枚为假币，而且假币的重量比真币的轻。假币和真币从外形看一模一样，无法分辨出来。请从中找出这枚假币。

分析：

例3-8：归并排序。

某数列存储在序列A[1]，A[2]，……，A[n]，现采用归并思想进行排序。

分析：

例3-8的N-S图

序列（5，3，4，2，1，3，6，2）进行归并排序的示例图