1.介紹
分治法是一種很重要的算法。字面上的解釋是“分而治之”，就是把一個復(fù)雜的問題分成兩個或更多的相同或相似的子問題咧栗，再把子問題分成更小的子問題……直到最后子問題可以簡單的直接求解冈钦，原問題的解即子問題的解的合并居凶。這個技巧是很多高效算法的基礎(chǔ)，如排序算法(快速排序躯喇，歸并排序)辫封，傅立葉變換(快速傅立葉變換)……
2.可解決的問題
二分搜索
大整數(shù)乘法
棋盤覆蓋
合并排序
快速排序
線性時間選擇
最接近點對問題
循環(huán)賽日程表
漢諾塔
3.步驟
分解: 將原問題分解為若干個規(guī)模較小, 相互獨立,與原問題形式相同的子問題
解決:若子問題規(guī)模較小而容易被解決則直接解, 否則遞歸的解各個子問題
合并:將各個子問題的解合并為原問題的解
4.設(shè)計模式
image.png
5.實踐 - 漢諾塔
5.1 漢諾塔的傳說
漢諾塔：漢諾塔（又稱河內(nèi)塔）問題是源于印度一個古老傳說的益智玩具。
大梵天創(chuàng)造世界的時候做了三根金剛石柱子廉丽，在一根柱子上從下往上按照大小順序摞著 64 片黃金圓盤倦微。大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。并且規(guī)定正压，在小圓盤上不能放大圓盤欣福，在三根柱子之間一次只能移動一個圓盤。
假如每秒鐘一次, 共需多長時間呢焦履？移完這些金片需要 5845.54 億年以上拓劝，太陽系的預(yù)期壽命據(jù)說也就是數(shù)百億年雏逾。真的過了 5845.54 億年，地球上的一切生命郑临，連同梵塔栖博、廟宇等，都早已經(jīng)灰飛煙滅
5.2 思路分析
- 如果是有個盤, A->C
如果我們有 n>= 2情況, 我們總是可以看做兩個盤 1最下邊盤 2.上面的盤
先把 最上面的盤 A->B
把最下邊的盤 A->C
把B塔的所有盤 從B->C
5.3 代碼實現(xiàn)
public class HanoiTower {
public static void main(String[] args) {
hanoiTower(5, 'A', 'B', 'C');
}
/**
* @param num
* @param a
* @param b
* @param 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, 移動過程 會使用到 A
hanoiTower(num-1, b, a,c);
}
}
}
