分治法在每一層遞歸上都有三個(gè)步驟
- 分解：將原問題分解為若干個(gè)規(guī)模較小哨苛，相互獨(dú)立蒙揣，與原問題形式相同的子問題
- 解決：若子問題規(guī)模較小而容易被解決則直接解決，否則遞歸的解各個(gè)子問題
- 合并：將各個(gè)子問題的解合并為原問題的解
漢諾塔問題描述
有三根桿(編號A所袁、B父泳、C)，在A桿自下而上窃判、由大到小按順序放置64個(gè)金盤钞楼。游戲的目標(biāo)：把A桿上的金盤全部移到C桿上，并仍保持原有順序疊好袄琳。操作規(guī)則：每次只能移動一個(gè)盤子询件，并且在移動過程中三根桿上都始終保持大盤在下燃乍，小盤在上，操作過程中盤子可以置于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("第一個(gè)盤從" + a + "->" + c);
} else {
// 如果我們有n>=2情況嘿辟，我們總是可以看做是兩個(gè)盤座咆，1.最下邊的一個(gè)盤 2.上邊所有盤
// 1.先把最上邊的所有盤A -> B，移動過程會用到c
hanoiTower(num - 1, a, c, b);
// 2. 把最下邊的盤A->C
System.out.println("第" + num + "個(gè)盤從" + a + "->" + c);
// 3. 把B所有盤從B->C仓洼，移動過程使用A
hanoiTower(num - 1, b, a, c);
}
}
}
