一. 算法介紹：
分治算法隶糕，其實(shí)就是把一個(gè)大問題看成若干個(gè)小問題奕扣，解決了所有的小問題，那么大問題就解決了待诅，原問題的解就是子問題解的合并孙援，之前說的歸并排序害淤、快速排序，都用到了分治思想拓售。
二. 分治算法的基本步驟：
分解：將原問題分解成若干個(gè)相互獨(dú)立的窥摄、規(guī)模較小的、容易求解的础淤、與原問題形式相同的子問題崭放；
解決：直接求解子問題或者遞歸求解子問題哨苛；
合并：將各個(gè)子問題的解合并為原問題的解。
三. 分治算法經(jīng)典應(yīng)用：漢諾塔問題
1. 漢諾塔問題介紹：
漢諾塔
漢諾塔問題介紹
2. 怎么玩币砂？
玩法
3. 思路分析：
我們先給3根針標(biāo)上號(hào)建峭，左邊的是A，中間的是B决摧，右邊的是C亿蒸。
假如只有一個(gè)盤，那就直接從A移動(dòng)到C蜜徽；
假如有兩個(gè)盤祝懂，那就把上面那個(gè)從A移動(dòng)到B，把底下那個(gè)從A到C拘鞋，再把B中的移到C砚蓬；
假如有多個(gè)盤，我們也可以按照兩個(gè)盤的方式處理盆色。即把最下邊的看成一個(gè)盤灰蛙，其他所有的看成一個(gè)盤；當(dāng)然這里其他所有的還可以按照這種方式再進(jìn)行分治隔躲。
4. 代碼實(shí)現(xiàn)：
public class HanoiTower {
/**
* 漢諾塔問題
* @param plateNum 盤子的數(shù)量
* @param a 出發(fā)地摩梧，初始的時(shí)候是A
* @param b 中轉(zhuǎn)地，初始的時(shí)候是B
* @param c 目的地宣旱，初始的時(shí)候是C
*/
public static void hanoiTower(int plateNum, String a, String b, String c) {
if (plateNum == 1) {
System.out.println("從 " + a + " 到 " + c);
} else { // 盤子數(shù)量大于等于2的情況
// 上面的從A到B
hanoiTower(plateNum - 1, a, c, b);
// 最下面那個(gè)從A到C
System.out.println("從 " + a + " 到 " + c);
// B針上的所有搬到C
hanoiTower(plateNum - 1, b, a, c);
}
}
public static void main(String[] args) {
hanoiTower(5, "A", "B", "C");
}
}
怎么驗(yàn)證對(duì)不對(duì)呢仅父？打開4399或者7k7k，搜索漢諾塔浑吟，選擇盤子的數(shù)量笙纤，運(yùn)行代碼，按照代碼打印的結(jié)果去玩這個(gè)游戲组力，就知道對(duì)不對(duì)了省容。
