分治算法的步骤
分治算法在每一层递归上都有三个步骤：
- 分解：将原问题分解为若干个规模较小、相互独立、与原问题形式相同的子问题。
- 解决：若子问题规模较小而容易被解决则直接解决，否则递归地求解各个子问题。
- 合并：将各个子问题的解合并为原问题的解。
分治算法的经典例题
分治算法可以求解的经典问题包括：
- 二分搜索（待补充）
- 大整数乘法
- Strassen矩阵乘法
- 棋盘覆盖
- 合并排序（待补充）
- 快速排序（待补充）
- 线性时间选择
- 最接近点对问题
- 循环赛日程表
- 汉诺塔
下面以“汉诺塔问题”为例说明分治算法的思想。
汉诺塔问题
设n为盘子的数量。
- 对于 n=1 的情况，直接将盘子从A杆移动到C杆。
对于 n≥2 的情况，可以将问题分解为：
- 把 n-1 个盘子从A移动到B；
- 把第 n 个盘子从A移动到C；
- 把 n-1 个盘子从B移动到C。
那么，怎么把 n-1 个盘子从一根杆子移动到另一根杆子上呢？可以先把 n-2 个盘子先移动，再移动第 n-1 个盘子……这就是分治法的思想。
因此可以很容易地写出汉诺塔问题的算法：
public class HanoiTower {
public static void main(String[] args) {
int n = 5;
hanoiTower(n, 'A', 'B', 'C');
}
public static void hanoiTower(int num, char a, char b, char c) {
// 对于 n = 1 的情况，直接将盘子从A杆移动到C杆。
if (num == 1) {
System.out.println("第" + num + "个盘: " + a + " -> " + c);
}
// 对于 n ≥ 2 的情况
else {
// 把 n - 1 个盘子从A移动到B；
hanoiTower(num - 1, a, c, b);
// 把第 n 个盘子从A移动到C；
System.out.println("第" + num + "个盘: " + a + " -> " + c);
// 把 n - 1 个盘子从B移动到C。
hanoiTower(num - 1, b, a, c);
}
}
}