分治法 是一種很重要的算法。字面上的解釋是 <code>分而治之</code>，把一個複雜的問題 分成兩個或更多的相同或相似的子問題，再把子問題分成更小的子問題.... 直到最後子問題可以簡單的直接求解，原問題的解即 子問題的解的合并。
這個技巧是很多高效算法的基礎，比如 排序算法：快速排序、歸并排序，傅裡葉變換、快速傅裡葉變換
分治算法可以 求解的一些經典問題 如：
二分搜尋
大整數乘法
棋盤覆寫
快速排序
歸并排序
線性時間選擇
最接近點對問題
循環賽日程表
漢諾塔
回過頭看了下之前的快速排序和歸并排序，他們也是難點在于如何把一個大問題 分解 成一個小問題進行 解決，然後再 合并 小問題的結果。
分治法在每一層遞歸上都有三個步驟：
<code>分解</code>：将原問題分解為若幹個規模較小、互相獨立、與原問題形式相同的子問題
<code>解決</code>：若子問題規模較小而容易被解決則直接解決，否則遞歸的解各個子問題
<code>合并</code>：将各個子問題的解合并為原問題的解
分治（Divide-and-Conquer(P)）的算法設計模式如下：
<code>|P|</code>：表示問題 P 的規模
<code>n0</code>：為閥值，表示當問題 P 的規模不超過 n0 時，問題已容易直接解出，不必再繼續分解
<code>ADHOC(P)</code> ：該分治法中的基本子算法，用于直接解小規模的問題 P
是以，當 P 的規模不超過 n0 時，直接用 <code>ADHOC(P)</code> 求解。
<code>MERGE(y1,y2,..yk)</code>：該分治法中的合并子算法，用于将 P 的子問題 P1、P2...Pk 的相應的解 y1、y2...yk 合并為 P 的解
漢諾塔（又稱河内塔）問題是源于印度一個古老傳說的益智玩具。大梵天創造世界的時候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞着 64 片黃金圓盤。大梵天指令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。并且規定，在小圓盤上不能放大圓盤，在三根柱子之間一次隻能移動一個圓盤。
假如每秒鐘一次，共需多長時間呢？移完這些金片需要 5845.54 億年以上，太陽系的預期壽命據說也就是數百億年。真的過了 5845.54 億年，地球上的一切生命，連同梵塔、廟宇等，都早已經灰飛煙滅。
如上圖所示：
隻有一個盤的時候：直接從 A → C
有兩個盤的時候：
A → B
A → C
B → C
有三個盤的時候：
C → B
B → A
從以上步驟來看：
當隻有一個盤時，需要走 1 步
當有兩個盤時，需要走 3 步
當有三個盤時，需要走 7 步
當有 3 個盤的時候，就很複雜了：
我們就将最小問題規模限定為 1，隻有一個盤時：A → C
當有 <code>n ≥ 2</code> 的情況，我們總是可以看做是兩個盤：
最下邊的盤
最上邊的盤
那麼執行兩個盤的操作步驟：
A → B：最上面的盤移動
A → C：最下面的盤移動
B → C：最上面的盤移動
測試輸出:
1 個盤
2 個盤
3 個盤
4 個盤
5 個盤
盤子越大編号越小，上面的第 n 個盤是和盤子大小對應的。
代碼簡單，但是這個為什麼會實作這種效果，筆者還是看得很懵逼。最主要的是如何分解，學算法是要了解它的思想。
這裡主要的難點在于：
分解到隻有 1 個盤子時，才會移動第一步
每次分解，那個 a、b、c 代表的柱子，完全不一樣
靠腦袋去分析這個流程很難，隻能當問題規模足夠小的時候，比如隻有 1 個盤子，隻有 2 個盤子時，你還很容易厘清楚，多了遞歸下去，你就搞不懂了