• 分治算法的介紹
• 經(jīng)典問題
• 基本步驟
• 漢諾塔
  • 思路分析
  • 代碼實現(xiàn)

1.分治算法的介紹

• 分治算法。字面意思就是 “分而治之” 。 就是把一個復(fù)雜的問題分成多個相同或相似的子問題，再把子問題分成更小的子問題....直到最后的子問題可以簡單的直接求解，原問題的解即子問題解的合并。

2. 分治算法的經(jīng)典問題

• 二分搜索
• 大整數(shù)乘法
• 棋盤覆蓋
• 合并排序
• 快速排序
• 線性時間選擇
• 最接近點對問題
• 循環(huán)賽日程表
• 漢諾塔

3. 基本步驟

• 分治法在每層遞歸都有三個步驟

分解： 將原問題分解為若干個小規(guī)模的與原問題形式相同的子問題

解決： 若子問題規(guī)模較小而容易被解決則直接解，否則遞歸地解各個子問題

合并： 將各個子問題的解合并為原問題的解

4. 漢諾塔

• 思路分析：

  (1)如果有一個盤， A->C

  如果 n >= 2 的情況，可以看作是兩個盤，1.最下邊的盤，2.上面的盤

  (2) 先把 最上面的盤 從 A移到B

  (3) 把最下邊的盤從 A 移到 C

  (4) 把 B 的所有盤移到 C

• 代碼實現(xiàn)

public class Hanoitower {
    public static void main(String[] args) {
        hanoiTower(5,'A','B','C');
    }
    //漢諾塔的移動方法
    //使用分治算法
    public static void hanoiTower(int num,char a,char b,char c){
        //如果只有一個盤
        if(num == 1){
            System.out.println("第1個盤從" + 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
            hanoiTower(num - 1,b,a,c);

        }
    }
}