一、算法思路
1、思路
分治算法的思想是：对于一个规模为N的问题，若该问题可以容易解决(比如规模N较小)，则直接解决，否则将其分解为M个规模较小的子问题，这些子问题互相独立，并且与原问题形式相同，递归的解决这些子问题，然后将各子问题的解合并得到原问题的解
2、分治法适用范围
一般具有以下特征的问题可以使用分治算法求解：
(1)求解问题可以分解为若干个规模较小的相同问题
(2)求解问题的规模分解到一定程度，就能够很容易地求解
(3)合并子问题的解可以得到问题的解
(4)由求解问题所分解的各个子问题是互相独立的
3、分治法的步骤
(1)分解：将要求解的问题划分为规模较小的同类问题
(2)求解：当子问题划分的足够小的时候，用比较简单的方法求解，得到子问题的解
(3)合并：按求解问题的要求，将子问题的解逐层合并，即可构成最终的解
二、分治法实例：比赛日程的安排
1、问题描述
某学校举行乒乓球比赛，在初赛阶段设置为循环赛，设有n位选手参赛，初赛共进行n-1天，每位选手要与其他每一位选手进行一场比赛，然后按积分排名选拔进入决赛的选手。根据学校作息时间，要求每位选手每天必须比赛一场，不能轮空。按此要求为比赛安排具体日程，即决定每天各选手对阵的对手
2、解题思路
可考虑使用分治法来简化日程的安排。按照分治策略，可以将所有的参赛选手分为两半，则n个选手的比赛日程可以通过n/2个选手比赛日程来决定。继续用这种一分为二方法对选手进行划分，直到只剩2位选手时情况就很简单了
设n位参赛选手按顺序编号为1,2,3,…,n，比赛的日程表制作为一个二维表格，其中每一行为一位选手各天对阵的各选手编号，例如8位选手7天的比赛日程如下表所示：
在上表中，每一列表示当天的比赛安排，由左侧选手编号对阵当天这列中对应编号的选手，如：
第1天，1号选手对阵2号选手，3号选手对阵4号选手
第3天，1号选手对阵4号选手，3号选手对阵2号选手
对于8位选手的情况，仍然比较复杂，通过分治法将其分为两半，即只考虑4位选手的比赛情况，可以编写如下日程：
对于4位选手的对阵情况，可继续采用分治法，将4个选手的比赛分解为2个选手的情况来考虑。只有2个选手时，比赛日程的制定就变得很简单了，比赛只需要1天，有1号和2号选手对阵即可，如下图所示：
上面的分解过程可以描述如下：
在日程安排还有个重要问题，就是通过分治法将问题分解后，怎样将得到的结果合并在一起。观察4位选手的日程情况，可以看到一些规律：
1、第1天的日程只需将1、2号选手和3、4号选手的日程直接合并
2、第2、3天的日程相对就要复杂些，将4人的表格划分为4部分，这时会发现，将表格左下角的值复制到右上角，左上角复制到右下角即可
所以使用分治法，要找到合并结果的规律