一. 算法介紹：

分治算法，其實(shí)就是把一個(gè)大問題看成若干個(gè)小問題，解決了所有的小問題，那么大問題就解決了，原問題的解就是子問題解的合并，之前說的歸并排序、快速排序，都用到了分治思想。

二. 分治算法的基本步驟：

• 分解：將原問題分解成若干個(gè)相互獨(dú)立的、規(guī)模較小的、容易求解的、與原問題形式相同的子問題；

• 解決：直接求解子問題或者遞歸求解子問題；

• 合并：將各個(gè)子問題的解合并為原問題的解。

三. 分治算法經(jīng)典應(yīng)用：漢諾塔問題

1. 漢諾塔問題介紹：

漢諾塔

漢諾塔問題介紹

2. 怎么玩？

玩法

3. 思路分析：

我們先給3根針標(biāo)上號，左邊的是A，中間的是B，右邊的是C。

• 假如只有一個(gè)盤，那就直接從A移動到C；

• 假如有兩個(gè)盤，那就把上面那個(gè)從A移動到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)證對不對呢？打開4399或者7k7k，搜索漢諾塔，選擇盤子的數(shù)量，運(yùn)行代碼，按照代碼打印的結(jié)果去玩這個(gè)游戲，就知道對不對了。