??????? 前置文章：遞歸算法：m.itdecent.cn/p/703069f3ba3f .
??????? 漢諾塔問題是來(lái)源于印度傳說(shuō)中的一個(gè)問題，這個(gè)傳說(shuō)是法國(guó)數(shù)學(xué)家愛德華·盧卡斯發(fā)明并編寫的(維基百科/百度百科)。
? ? ? ? 漢諾塔問題的傳說(shuō)是這么描述的：大梵天創(chuàng)造世界的時(shí)候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤。大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。并且規(guī)定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動(dòng)一個(gè)圓盤。問題的描述非常清楚，理解不了在某寶搜索漢諾塔，有各種造型的漢諾塔玩具，也就理解了。
???????
??????? 這個(gè)樣子漢諾塔問題就從一個(gè)抽象的問題成為了具體可見的問題，只要求問題的解就好。漢諾塔問題怎么考慮呢，我們這么來(lái)考慮這個(gè)問題。
??????? 我現(xiàn)在手頭有三根柱子x、y、z，然后有三個(gè)圓盤a、b、c，為什么是三個(gè)，因?yàn)槿齻€(gè)我還能操作，如果是傳說(shuō)中的64個(gè)，我要是能轉(zhuǎn)移完，那我就是傳說(shuō)了。總之，我手上這三個(gè)圓盤是按照大小排列的，也就是c最小，在最上，a最大，在最下，現(xiàn)在三個(gè)圓盤放在x柱子上，我的目的是將圓盤轉(zhuǎn)移到z柱子上。
??????? 首先，我將c從x轉(zhuǎn)移到z：c -> z. 將b轉(zhuǎn)移到y(tǒng)：b -> y.? 現(xiàn)在圓盤的狀態(tài)是：x：a；y：b；z：c。我要將圓盤最后轉(zhuǎn)移到z柱子上，那a應(yīng)該是在最下面，所以，我將c轉(zhuǎn)移到y(tǒng)柱子，也就是b上面。這樣z柱子就空下來(lái)了，我將a轉(zhuǎn)移到z柱子上?，F(xiàn)在圓盤的狀態(tài)：x；y：b\c；z：a。那么我已經(jīng)達(dá)成了從x柱子轉(zhuǎn)移a圓盤到z圓盤，最大的盤子已經(jīng)轉(zhuǎn)移過去了?，F(xiàn)在的問題就成了從y柱子上將兩個(gè)圓盤轉(zhuǎn)移到z柱子上面，問題的規(guī)模變小了，成立兩個(gè)盤子的問題。兩個(gè)圓盤的問題好解決，我將c轉(zhuǎn)移到x柱子，然后將b放到z柱子的a圓盤上，將c轉(zhuǎn)到z柱子的b圓盤上，問題就解決了。
??????? 我剛剛是在三個(gè)圓盤的基礎(chǔ)上解決這個(gè)問題，在解決過程中，我最早要達(dá)到的目的是將a圓盤，也就是最大的圓盤先轉(zhuǎn)移到目標(biāo)柱子，轉(zhuǎn)移之后問題的規(guī)模就小了一個(gè)圓盤，成了兩個(gè)圓盤的漢諾塔問題。那么當(dāng)我有四個(gè)圓盤的時(shí)候，我最先應(yīng)該達(dá)成的目標(biāo)不就是先將最大的那個(gè)圓盤轉(zhuǎn)移到目標(biāo)柱子上么，那么問題的規(guī)模就減小到了三個(gè)圓盤的問題。那當(dāng)我有64個(gè)圓盤的時(shí)候，我需要做的是將最下面的圓盤轉(zhuǎn)移，然后問題就成了63個(gè)圓盤的問題，63個(gè)圓盤的問題再繼續(xù)精簡(jiǎn)......問題就轉(zhuǎn)化成了一個(gè)遞歸問題，從遞歸的思路來(lái)解決這個(gè)問題就簡(jiǎn)單許多了。
??????? 漢諾塔可以用數(shù)組或者是數(shù)據(jù)結(jié)構(gòu)棧進(jìn)行實(shí)現(xiàn)。
void hanoi( int n, stack<int>x, stack<int>y, stack<int>z ) {
??????? if ( n==0) return;
??????? hanoi( n-1, x, z, y);??????? //將n-1 個(gè)圓盤從x柱子轉(zhuǎn)移到y(tǒng)柱子
??????? z.push(x.pop());??????????? //將x柱子最后的一個(gè)圓盤轉(zhuǎn)移到z柱子
??????? hanoi( n-1, y, z, x);??????? //將n-1 個(gè)圓盤從y柱子轉(zhuǎn)移到x柱子，還原操作，將圓盤位置還原，便于遞歸操作
}
??????? 算法的時(shí)間復(fù)雜度經(jīng)過統(tǒng)計(jì)會(huì)發(fā)現(xiàn)是2^n-1，非常高的復(fù)雜度，所以，如果有64個(gè)圓盤，讓我一步一步的轉(zhuǎn)移，如果我能轉(zhuǎn)移完，那我會(huì)成為傳奇，畢竟2^64-1的操作步數(shù)，我就算1s操作一步，我大概也能活到幾百億年的樣子，當(dāng)然，我可能并不介意活這么久。
? ? ? ? 我用了幾分鐘寫的一道算法，我用了幾個(gè)簡(jiǎn)單的步驟就做出的算法，它的執(zhí)行時(shí)間卻幾乎能夠讓地球體會(huì)到破滅的感覺。嗬，有限步的程序==無(wú)限步的運(yùn)算。 ?????
