??????? 前置文章：遞歸算法：www.reibang.com/p/703069f3ba3f .
??????? 漢諾塔問題是來源于印度傳說中的一個問題假栓，這個傳說是法國數(shù)學家愛德華·盧卡斯發(fā)明并編寫的(維基百科/百度百科)。
? ? ? ? 漢諾塔問題的傳說是這么描述的：大梵天創(chuàng)造世界的時候做了三根金剛石柱子霍掺，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤匾荆。大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上拌蜘。并且規(guī)定，在小圓盤上不能放大圓盤牙丽，在三根柱子之間一次只能移動一個圓盤简卧。問題的描述非常清楚，理解不了在某寶搜索漢諾塔烤芦，有各種造型的漢諾塔玩具举娩，也就理解了。
???????
??????? 這個樣子漢諾塔問題就從一個抽象的問題成為了具體可見的問題构罗，只要求問題的解就好铜涉。漢諾塔問題怎么考慮呢，我們這么來考慮這個問題遂唧。
??????? 我現(xiàn)在手頭有三根柱子x骄噪、y、z蠢箩，然后有三個圓盤a链蕊、b、c谬泌，為什么是三個滔韵，因為三個我還能操作，如果是傳說中的64個掌实，我要是能轉移完陪蜻，那我就是傳說了〖牵總之宴卖，我手上這三個圓盤是按照大小排列的，也就是c最小邻悬，在最上症昏，a最大，在最下父丰，現(xiàn)在三個圓盤放在x柱子上肝谭，我的目的是將圓盤轉移到z柱子上。
??????? 首先蛾扇，我將c從x轉移到z：c -> z. 將b轉移到y(tǒng)：b -> y.? 現(xiàn)在圓盤的狀態(tài)是：x：a攘烛；y：b；z：c镀首。我要將圓盤最后轉移到z柱子上坟漱，那a應該是在最下面，所以更哄，我將c轉移到y(tǒng)柱子芋齿，也就是b上面腥寇。這樣z柱子就空下來了，我將a轉移到z柱子上」低唬現(xiàn)在圓盤的狀態(tài)：x花颗；y：b\c；z：a惠拭。那么我已經(jīng)達成了從x柱子轉移a圓盤到z圓盤扩劝，最大的盤子已經(jīng)轉移過去了。現(xiàn)在的問題就成了從y柱子上將兩個圓盤轉移到z柱子上面职辅，問題的規(guī)模變小了棒呛，成立兩個盤子的問題。兩個圓盤的問題好解決域携，我將c轉移到x柱子簇秒，然后將b放到z柱子的a圓盤上，將c轉到z柱子的b圓盤上秀鞭，問題就解決了趋观。
??????? 我剛剛是在三個圓盤的基礎上解決這個問題，在解決過程中锋边，我最早要達到的目的是將a圓盤皱坛，也就是最大的圓盤先轉移到目標柱子，轉移之后問題的規(guī)模就小了一個圓盤豆巨，成了兩個圓盤的漢諾塔問題剩辟。那么當我有四個圓盤的時候，我最先應該達成的目標不就是先將最大的那個圓盤轉移到目標柱子上么往扔，那么問題的規(guī)模就減小到了三個圓盤的問題贩猎。那當我有64個圓盤的時候，我需要做的是將最下面的圓盤轉移萍膛，然后問題就成了63個圓盤的問題吭服，63個圓盤的問題再繼續(xù)精簡......問題就轉化成了一個遞歸問題，從遞歸的思路來解決這個問題就簡單許多了卦羡。
??????? 漢諾塔可以用數(shù)組或者是數(shù)據(jù)結構棧進行實現(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 個圓盤從x柱子轉移到y(tǒng)柱子
??????? z.push(x.pop());??????????? //將x柱子最后的一個圓盤轉移到z柱子
??????? hanoi( n-1, y, z, x);??????? //將n-1 個圓盤從y柱子轉移到x柱子，還原操作绿饵，將圓盤位置還原，便于遞歸操作
}
??????? 算法的時間復雜度經(jīng)過統(tǒng)計會發(fā)現(xiàn)是2^n-1瓶颠，非常高的復雜度拟赊，所以，如果有64個圓盤粹淋，讓我一步一步的轉移吸祟，如果我能轉移完瑟慈，那我會成為傳奇，畢竟2^64-1的操作步數(shù)屋匕，我就算1s操作一步葛碧，我大概也能活到幾百億年的樣子，當然过吻，我可能并不介意活這么久进泼。
? ? ? ? 我用了幾分鐘寫的一道算法，我用了幾個簡單的步驟就做出的算法纤虽，它的執(zhí)行時間卻幾乎能夠讓地球體會到破滅的感覺乳绕。嗬，有限步的程序==無限步的運算逼纸。 ?????
