同学们都想考个好成绩， 把目标分成语文、 数学、英语都考个好成绩，然后继续分下去，比如数学分成图形问题，计算问题等， 计算问题分成凑整计算，拆分计算等，一直分到我们要掌握的每个小技巧。这就是学习中的分治 — 各个击破。
问题：有若干枚硬币中混入了 1枚伪币，伪币从外表看与真币一样，但由于材质不同，因此伪币比真币要轻一些。现在给你提供一台天平，请你用最快的速度找出此枚伪币。
分治 将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。
即一种分目标完成程序算法。 分治法解题的一般步骤：
(1) 分解，将要解决的问题划分成若干规模较小的同类问题；
(2) 求解，当子问题划分得足够小时，用较简单的方法解决；
(3) 合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。
运用分治策略解决的问题一般来说具有以下特点:
1、 原问题可以分解为多个子问题
这些子问题与原问题相比，只是问题的规模有所降低，其结构和求解方法与原问题相同或相似。
2、 原问题在分解过程中，递归地求解子问题
由于递归都必须有一个终止条件，因此，当分解后的子问题规模足够小时，应能够直接求解。
3、 在求解并得到各个子问题的解后，应能够釆用某种方式、方法合并或构造出原问题的解。 不难发现，在分治策略中，由于子问题与原问题在结构和解法上的相似性，用分治方法解决 的问题，大都釆用了递归的形式。
分治的典型应用：
● 二分查找的递归解法
● 插值查找
● 快速排序
● 归并排序
分类