目錄

1. 什么是漢諾塔

2.?三座臺(tái)柱的漢諾塔

2.1 思路

2.2?三座臺(tái)柱的漢諾塔代碼

3. 四座臺(tái)柱的漢諾塔

3.1 思路

3.2 四座臺(tái)柱的漢諾塔代碼

---

1. 什么是漢諾塔

漢諾塔代碼的功能：計(jì)算盤子的移動(dòng)次數(shù)，由數(shù)學(xué)公式知，漢諾塔的盤子移動(dòng)次數(shù)與盤子數(shù)n存在這樣的關(guān)系，移動(dòng)數(shù) =（由遞推得到），后面可以用這個(gè)公式來驗(yàn)證我們代碼。

漢諾塔的規(guī)制：（1）有三根相鄰的柱子，標(biāo)號(hào)為A,B,C。（2）A柱子上從下到上按金字塔狀疊放著n個(gè)不同大小的圓盤。（3）現(xiàn)在把所有盤子一個(gè)一個(gè)移動(dòng)到柱子B上，并且每次移動(dòng)同一根柱子上都不能出現(xiàn)大盤子在小盤子上方。

2.?三座臺(tái)柱的漢諾塔

2.1 思路

總結(jié)：我們想知道n個(gè)盤子的次數(shù)，記住了，在求解f(n)的時(shí)候，我們直接默認(rèn)f(n - 1)已經(jīng)完了就可以了！這個(gè)在前面已經(jīng)解釋過了，在此不再鰲述。我們將n-1個(gè)盤子當(dāng)作一個(gè)整體：這就是類似于分治求解子問題的思想

那么當(dāng)由3個(gè)盤子時(shí)，就有公式：f(3,x,y,z) = f(2,x,z,y),x->z,f(2,y,x,z)；當(dāng)有4個(gè)盤子時(shí)，就有公式：f(4,x,y,z) = f(3,x,z,y),x->z,f(3,y,x,z).從而推出f(n,x,y,z) = f(n,x,z,y),x->z,f(n,y,x,z)!
?

綜上所述：也就是說我們想移動(dòng)n個(gè)盤子，就需要先移動(dòng)n - 1個(gè)盤子；移動(dòng)n - 1個(gè)盤子，就需要先移動(dòng)n - 2個(gè)盤子 ………………；移動(dòng)2個(gè)盤子，就必須先移動(dòng)1個(gè)盤子；

（1）而移動(dòng)1個(gè)盤子就是遞歸的終止條件

（2）而n個(gè)盤子變成n - 1個(gè)盤子就是遞歸的大問題變成小問題的方法

2.2?三座臺(tái)柱的漢諾塔代碼

下列代碼展示了盤子在柱子上移動(dòng)的順序：

下列代碼展示了有n個(gè)盤子，至少移動(dòng)幾次：

對(duì) （展示了有n個(gè)盤子，至少移動(dòng)幾次）解析：

ps：小伙伴們，圖片將就著看吧哈哈哈，gif制作軟件的免費(fèi)用戶是這樣的w(ﾟДﾟ)w！

?通過3個(gè)盤子，我們可以分析得：

（1）想先移動(dòng)第3個(gè)盤子到最終位置，就必須先移動(dòng)上面2個(gè)盤子；

（2）上面2個(gè)盤子總共移動(dòng)了兩趟，這就是2 * moveCount3(n - 1)的原因；

（3）最底下的盤子是移動(dòng)了一次，這就是2 * moveCount3(n - 1) + 1的原因；

總結(jié)：

有n個(gè)盤子，上面n - 1個(gè)盤子需要移動(dòng)兩趟，而最底下，也就是第n個(gè)盤子是移動(dòng)1次！！！

3. 四座臺(tái)柱的漢諾塔

3.1 思路

算法思想:
用如下算法移動(dòng)盤子(記為fourHanoi):
將A柱上n個(gè)盤子劃分為上下兩部分，上方部分共有m(1≤m≤n)個(gè)盤子，下方部分共有n - m個(gè)盤子。
步驟一：將A柱上面部分m個(gè)盤子使用fourHanoi算法經(jīng)過C、D柱移至B柱。（此時(shí)C、D是中間柱）
步驟二：將A柱剩余的n - m個(gè)盤子使用threeHanoi算法經(jīng)過C柱移至D柱。（此時(shí)C柱是中間柱）
步驟三：將B柱上的m個(gè)盤子使用fourHanoi算法經(jīng)過A、C柱移至D柱。（此時(shí)A、C柱是中間柱）

這就有伙伴有疑問了，為什么不能全部都使用fourHanoi算法？

答：因?yàn)楫?dāng)fourHanoi算法將盤子轉(zhuǎn)移到一定程度后，有個(gè)柱子上的盤子就不能動(dòng)了，可以當(dāng)作少了座臺(tái)柱，也就是只能用threeHanoi算法移動(dòng)其它盤子了。所以我們?cè)谟?jì)算的時(shí)候，就是在找fourHanoi算法將盤子轉(zhuǎn)移到一定程度的臨界值，也就是找多少個(gè)盤子能使用fourHanoi算法（找m）

根據(jù)算法的思想，可知：

（1）最優(yōu)子結(jié)構(gòu)性質(zhì):
四柱漢諾塔問題的最優(yōu)解是用最少的移動(dòng)次數(shù)將A柱上的盤子全部移到D柱上。當(dāng)盤子總數(shù)為i時(shí)，我們不妨設(shè)使用fourHanoi的最少移動(dòng)次數(shù)為f(i)。相應(yīng)的threeHanoi 算法移動(dòng)次數(shù)為g(n - m)，由于g(n - m)=2g(n - m - 1)+1=2^(n - m)?-1,當(dāng)n - m確定時(shí)，g(n - m)也是不變的。
f(m)為最優(yōu)解時(shí)，其子問題f(m - 1)也必為最優(yōu)解。如果f(m - 1)不是最優(yōu)解，那么存在f’(m - 1) < f(m - 1)。用f’(m - 1)替換f(m - 1)將產(chǎn)生一個(gè)比f(m)更優(yōu)的解。這與f(m)為最優(yōu)解是矛盾的。所以本問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。
（2）遞歸地定義問題的最優(yōu)解:

根據(jù)上述fourHanoi算法得到最少移動(dòng)次數(shù)f(m):

①當(dāng)n = 1時(shí)，有

②當(dāng)n > 1時(shí)，有

3.2 四座臺(tái)柱的漢諾塔代碼