分治法在每一层递归上都有三个步骤
- 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题
- 解决：若子问题规模较小而容易被解决则直接解决，否则递归的解各个子问题
- 合并：将各个子问题的解合并为原问题的解
汉诺塔问题描述
有三根杆(编号A、B、C)，在A杆自下而上、由大到小按顺序放置64个金盘。游戏的目标：把A杆上的金盘全部移到C杆上，并仍保持原有顺序叠好。操作规则：每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，小盘在上，操作过程中盘子可以置于A、B、C任一杆上。
public class HanoiTower {
public static void main(String[] args) {
}
public static void hanoiTower(int num, char a, char b, char c) {
if (num == 1) {
System.out.println("第一个盘从" + a + "->" + c);
} else {
// 如果我们有n>=2情况，我们总是可以看做是两个盘，1.最下边的一个盘 2.上边所有盘
// 1.先把最上边的所有盘A -> B，移动过程会用到c
hanoiTower(num - 1, a, c, b);
// 2. 把最下边的盘A->C
System.out.println("第" + num + "个盘从" + a + "->" + c);
// 3. 把B所有盘从B->C，移动过程使用A
hanoiTower(num - 1, b, a, c);
}
}
}
