漢諾塔遞歸算法&分析過(guò)程

漢諾塔遞歸算法&分析過(guò)程

漢諾塔：漢諾塔（又稱河內(nèi)塔）問(wèn)題是源于印度一個(gè)古老傳說(shuō)的益智玩具。大梵天創(chuàng)造世界的時(shí)候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤(pán)。大梵天命令婆羅門(mén)把圓盤(pán)從下面開(kāi)始按大小順序重新擺放在另一根柱子上。并且規(guī)定，在小圓盤(pán)上不能放大圓盤(pán)，在三根柱子之間一次只能移動(dòng)一個(gè)圓盤(pán)。

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

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

n=64時(shí)，

假如每秒鐘一次，共需多長(zhǎng)時(shí)間呢？一個(gè)平年365天有31536000 秒，閏年366天有31622400秒，平均每年31556952秒，計(jì)算一下：

18446744073709551615秒

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

漢諾塔問(wèn)題在數(shù)學(xué)界有很高的研究?jī)r(jià)值，而且至今還在被一些數(shù)學(xué)家們所研究，也是我們所喜歡玩的一種益智游戲，它可以幫助開(kāi)發(fā)智力，激發(fā)我們的思維。

之前看到了一段經(jīng)典的遞歸代碼，簡(jiǎn)簡(jiǎn)單單幾行代碼就解決了深?yuàn)W的問(wèn)題，為什么那幾行代碼就把漢諾塔問(wèn)題給解了呢？

代碼如下：

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

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

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

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

這個(gè)可以用二叉樹(shù)解釋。下面看一個(gè)圖估計(jì)你就會(huì)知道了。

這是一個(gè)遞歸的圖解，根結(jié)點(diǎn)是第一次進(jìn)入move函數(shù)，第一個(gè)參數(shù)3只要大于1就往下推，第二個(gè)參數(shù)是指要移動(dòng)的盤(pán)的原始位置，第四個(gè)參數(shù)是指要移動(dòng)到的目的位置，第三個(gè)參數(shù)中轉(zhuǎn)，下一次遞歸時(shí)準(zhǔn)備的一個(gè)參數(shù)。這個(gè)圖是按照程序畫(huà)出來(lái)的，上面的節(jié)點(diǎn)個(gè)數(shù)就是調(diào)用move函數(shù)的次數(shù)?，F(xiàn)在我們來(lái)中序遍歷這棵二叉樹(shù)。

假設(shè)：開(kāi)始時(shí)a,b,c三個(gè)盤(pán)都放在one上，從a到c依次增大，就是說(shuō)c放在最下面，a在最上面，-> 表示移動(dòng)。

節(jié)點(diǎn)4：a -> z

節(jié)點(diǎn)2：b -> y

節(jié)點(diǎn)5：a -> y

節(jié)點(diǎn)1：c -> z

節(jié)點(diǎn)6：a -> x

節(jié)點(diǎn)3：b -> z

節(jié)點(diǎn)7：a -> z

完成。

假設(shè)有4個(gè)盤(pán)呢？那也是一樣的道理可以推出。這時(shí)就有15個(gè)節(jié)點(diǎn)，就是說(shuō)要移動(dòng)15次。那有n個(gè)盤(pán)呢？2的n次方減1……