分治算法（ divide and conquer ）的核心思想其實就是四個字，分而治之 ，也就是将原問題劃分成 n 個規模較小，并且結構與原問題相似的子問題，遞歸地解決這些
子問題，然後再合并其結果，就得到原問題的解。
這個定義看起來有點類似遞歸的定義。關于分治和遞歸的差別，我們在排序（下）的時候講過，分治算法是一種處理問題的思想，遞歸是一種程式設計技巧。實際
上，分治算法一般都比較适合用遞歸來實作。分治算法的遞歸實作中，每一層遞歸都會涉及這樣三個操作：
分解：将原問題分解成一系列子問題；
解決：遞歸地求解各個子問題，若子問題足夠小，則直接求解；
合并：将子問題的結果合并成原問題。
分治算法能解決的問題，
一般需要滿足下面這幾個條件：
原問題與分解成的小問題具有相同的模式；
原問題分解成的子問題可以獨立求解，子問題之間沒有相關性，這一點是分治算法跟動态規劃的明顯差別，等我們講到動态規劃的時候，會詳細對比這兩種
算法；
具有分解終止條件，也就是說，當問題足夠小時，可以直接求解；
可以将子問題合并成原問題，而這個合并操作的複雜度不能太高，否則就起不到減小算法總體複雜度的效果了。
分治算法可以求解的一些經典問題
1二分搜尋 2大整數乘法 3 棋盤覆寫 4 合并排序 5 快速排序 6線性時間選擇 7 最接近點對問題 8 循環賽日程表 9 漢諾塔
分治(Divide-and-Conquer§)算法設計模式如下
分治算法的基本步驟
- 1 分治法在每一層遞歸上都有三個步驟：
- 2 分解：将原問題分解為若幹個規模較小，互相獨立，與原問題形式相同的子問題
- 3 解決：若子問題規模較小而容易被解決則直接解，否則遞歸地解各個子問題
- 4 合并：将各個子問題的解合并為原問題的解。
使用分治算法解決漢諾塔問題
漢諾塔問題
漢諾塔：漢諾塔（又稱河内塔）問題是源于印度一個古老傳說的益智玩具。大梵天創造世界的時候做了三根金
剛石柱子，在一根柱子上從下往上按照大小順序摞着 64 片黃金圓盤。大梵天指令婆羅門把圓盤從下面開始按大小
順序重新擺放在另一根柱子上。并且規定，在小圓盤上不能放大圓盤，在三根柱子之間一次隻能移動一個圓盤。
分析：
A 如果是有一個盤， A->C
B 如果我們有 n >= 2 情況，我們總是可以看做是兩個盤 1.最下邊的盤 2. 上面的盤
- 1 先把 最上面的盤 A->B
- 2 把最下邊的盤 A->C
- 3 把B塔的所有盤 從 B->C
可以看出 漢諾塔問題可以拆分成以上AB兩個大步，分解成的子問題可以獨立求解，子問題之間沒有相關性
如果有多個盤則分成AB 步驟，對AB步驟進行求解
設n個盤子的移動次數為T(n)
T(n)=2T(n-1)+1
T(1)=1
是以Hanoi塔算法的時間複雜度為O(2^n)
public class DivideAndConquer {
public static void main(String[] args) {
hanoiProblem(3, 'A', 'B', 'C');
}
/*
* @param: [discNum, discA, discB, discC]
* @return: void
* @author: Jerssy
* @dateTime: 2021/5/3 16:47
* @description:
*/
public static void hanoiProblem(int discNum,char discA,char discB,char discC){
if (discNum == 1) {
System.out.println("the 1 disc move from "+discA+"-->"+discC);
}
else {
hanoiProblem(discNum-1, discA, discC, discB);
System.out.println("the "+discNum+" disc move from "+discA+"-->"+discC);
hanoiProblem(discNum-1, discB, discA, discC);
}
}
}