- 分治算法的介紹
- 經(jīng)典問題
- 基本步驟
- 漢諾塔
- 思路分析
- 代碼實現(xiàn)
1.分治算法的介紹
- 分治算法贯卦。字面意思就是 “分而治之” 。 就是把一個復(fù)雜的問題分成多個相同或相似的子問題甘桑，再把子問題分成更小的子問題....直到最后的子問題可以簡單的直接求解拍皮，原問題的解即子問題解的合并歹叮。
2. 分治算法的經(jīng)典問題
- 二分搜索
- 大整數(shù)乘法
- 棋盤覆蓋
- 合并排序
- 快速排序
- 線性時間選擇
- 最接近點(diǎn)對問題
- 循環(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);
}
}
}
