漢諾塔遞歸算法&分析過程

漢諾塔遞歸算法&分析過程

漢諾塔：漢諾塔（又稱河內塔）問題是源于印度一個古老傳說的益智玩具。大梵天創造世界的時候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤。大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。并且規定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動一個圓盤。

不管這個傳說的可信度有多大，如果考慮一下把64片黃金圓盤，由一根柱子上移到另一根柱子上，并且始終保持上小下大的順序。這需要多少次移動呢?。1個的時候當然是1次，2個的時候是3次，3個的時候就用了7次......這實在是太累了。這里需要遞歸的方法。假設有n片，移動次數是f(n).顯然

f(1)=1,f(2)=3,f(3)=7，且f(k+1)=2f(k)+1。此后不難證明f(n)=2^n-1。

n=64時，

假如每秒鐘一次，共需多長時間呢？一個平年365天有31536000 秒，閏年366天有31622400秒，平均每年31556952秒，計算一下：

18446744073709551615秒

這表明移完這些黃金圓盤需要5845.54億年以上，而地球存在至今不過45億年，太陽系的預期壽命據說也就是數百億年。真的過了5845.54億年，不說太陽系和銀河系，至少地球上的一切生命，連同梵塔、廟宇等，都早已經灰飛煙滅。

漢諾塔問題在數學界有很高的研究價值，而且至今還在被一些數學家們所研究，也是我們所喜歡玩的一種益智游戲，它可以幫助開發智力，激發我們的思維。

之前看到了一段經典的遞歸代碼，簡簡單單幾行代碼就解決了深奧的問題，為什么那幾行代碼就把漢諾塔問題給解了呢？

代碼如下：

看到這個程序 ，難理解的就是下面兩句：

　　move(n-1, a, c, b)

　　move(n-1, b, a, c)

我們知道它用了遞歸，第一句把第一個位置的盤移到第二個位置，第二句再把第二個移到第三個位置。 但為什么這樣就可以遞歸出答案呢？

這個可以用二叉樹解釋。下面看一個圖估計你就會知道了。

這是一個遞歸的圖解，根結點是第一次進入move函數，第一個參數3只要大于1就往下推，第二個參數是指要移動的盤的原始位置，第四個參數是指要移動到的目的位置，第三個參數中轉，下一次遞歸時準備的一個參數。這個圖是按照程序畫出來的，上面的節點個數就是調用move函數的次數。現在我們來中序遍歷這棵二叉樹。

假設：開始時a,b,c三個盤都放在one上，從a到c依次增大，就是說c放在最下面，a在最上面，-> 表示移動。

節點4：a -> z

節點2：b -> y

節點5：a -> y

節點1：c -> z

節點6：a -> x

節點3：b -> z

節點7：a -> z

完成。

假設有4個盤呢？那也是一樣的道理可以推出。這時就有15個節點，就是說要移動15次。那有n個盤呢？2的n次方減1……