python遞歸——漢諾塔

漢諾塔的傳說

法國數學家

愛德華·盧卡斯 曾編寫過一個印度的古老傳說：在世界中心貝拿勒斯（在印度北部）的聖廟裡，一塊黃銅闆上插着三根寶石針。印度教的主神 梵天 在創造世界的時候，在其中一根針上從下到上地穿好了由大到小的64片金片，這就是所謂的漢諾塔。不論白天黑夜，總有一個僧侶在按照下面的法則移動這些金片：一次隻移動一片，不管在哪根針上，小片必須在大片上面。僧侶們預言，當所有的金片都從梵天穿好的那根針上移到另外一根針上時，世界就将在一聲霹靂中消滅，而 梵塔 、廟宇和衆生也都将同歸于盡。

　　不管這個傳說的可信度有多大，如果考慮一下把64片金片，由一根針上移到另一根針上，并且始終保持上小下大的順序。

　　這需要多少次移動呢?這裡需要遞歸的方法。假設有n片，移動次數是f(n).顯然f(1)=1,f(2)=3,f(3)=7，且f(k+1)=2*f(k)+1。此後不難證明f(n)=2^n-1。n=64時，

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

　　18446744073709551615秒

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

python漢諾塔

#函數的遞歸算法 漢諾塔遊戲
def hanoi(n,x,y,z):
    if n==1:
        print(x,'-->',z)
    else:
        hanoi(n-1,x,z,y)#将前n-1個盤子從x移動到y上
        hanoi(1,x,y,z)#将最底下的最後一個盤子從x移動到z上
        hanoi(n-1,y,x,z)#将y上的n-1個盤子移動到z上
n=int(input('請輸入漢諾塔的層數：'))
hanoi(n,'x','y','z')

》請輸入漢諾塔的層數：3
x --> z
x --> y
z --> y
x --> z
y --> x
y --> z
x --> z