前言
先講個故事，傳說古代印度有三根黃金柱，64個石盤，需要將石盤從第一根移動到第三根上，規定每次只能移動一片，并且小盤在放置時必須在大盤上。
當石盤移動完畢時，世界就會毀滅。
漢諾塔——遞歸
接下來我們用程序來模擬這個移動過程，并計算世界毀滅需要的時間。
這里使用的策略就是遞歸
我們將黃金柱編號為A,B,C,我們首先需要將A柱最底層的64號大石盤移動到C柱上，那么我們可以認為有一個大力士，將63號以及之前的石盤已經被放在了B柱上。B柱是輔助柱。這時，我們就可以輕松將A柱剩下的一個最大的64號石盤放到C柱上，此時我們完成了第一步。
同理，假設64號石盤已經被放在了C柱上，63號石盤此刻也需要被放在C柱上，我們也能認為，有一個大力士將62號以及之前的石盤已經被放在了B柱上。以此類推。
我們不用管大力士是如何做到的，我們每次只需要將最后一塊相對最大的石盤放到C柱上就行了。這就是每一次移動石盤最終的目的。
所以，每次在C柱上能夠正常進行疊放的最后一步都是，一個單獨的石盤等著被放在C柱上，我們輕松的將64號，63號，62號…1號放到C柱上
而實際上，大力士是我們遞歸的自己，這個又該怎么理解呢？
用python寫就是這樣
def hanoiTower(n,source,auxiliary,target):# 如果就剩下最后一塊，那么直接疊放到目標柱上，需要注意的是，目標柱并不是不變的，會變成輔助柱，因為搬運過程中，進入子遞歸，會把輔助柱當做目標柱，大力士需要先把63塊之前的所有石盤放到輔助柱上# 每次迭代，都將最后一塊設定為終極目標，搬完最后一塊就表明最后一個小任務完成了if n==1:print(f"{n}號石盤搬運：{source}-->{target}")else:#大力士將n-1塊石盤從源頭柱放到輔助柱，這樣最底層的石盤就暴露了出來# 將n-1個盤子從源柱移動到輔助柱（此時輔助柱成為子問題的目標柱）hanoiTower(n-1, source, target, auxiliary)print(f"{n}號石盤搬運：{source}-->{target}")# 大力士將n-1塊石盤從輔助柱放到目標柱，就算之前的任務完成了# 將n-1個盤子從輔助柱移動到目標柱（此時源柱成為子問題的輔助柱）hanoiTower(n-1, auxiliary,source, target )
hanoiTower(3,"A","B","C")
1號石盤搬運：A-->C
2號石盤搬運：A-->B
1號石盤搬運：C-->B
3號石盤搬運：A-->C
1號石盤搬運：B-->A
2號石盤搬運：B-->C
1號石盤搬運：A-->C
計算時間復雜度，空間復雜度，距離世界毀滅剩余的時間
每次任務分解，都是兩次移動n-1個盤子和一次移動單個盤子
因此T=2T(n-1)+1
根據實際情況可以將其展開，遞歸到第二次時T=2(2T(n-2)+1)+1
遞歸第三次時T=2(2*(2*T(n-3)+1))+1
一次類推展開，可以知道n=1時，就是遞歸結束的時候，此時T(1)=1
T=2^n-1
時間復雜度為O(2^n)
空間復雜度：
處理n個盤子時，遞歸調用鏈為n,n-1,n-2,n-3…1,最大深度所以為n,空間復雜度為O(n)
那么根據傳說，算出來2^64時間長度為11698.8483億年，這個時間說是宇宙末日，確實有可信度。
畢竟1萬億年以后的超人僧侶，1s就能抬起巨石將圓盤準確無誤的放到C黃金柱上，本宇宙漢諾塔也新修建完畢，宇宙終于再次放起了煙花，大爆炸開始了。
)
