漢諾塔-問題

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

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

不管這個傳說的可信度有多大，如果考慮一下把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億年，不說太陽系和銀河系，至少地球上的一切生命，連同梵塔、廟宇等，都早已經灰飛煙滅。

      和漢諾塔故事相似的，還有另外一個印度傳說：舍罕王打算獎賞國際象棋的發明人──宰相西薩·班·達依爾。國王問他想要什麼，他對國王說：“陛下，請您在這張棋盤的第1個小格裡賞給我一粒麥子，在第2個小格裡給2粒，第3個小格給4粒，以後每一小格都比前一小格加一倍。請您把這樣擺滿棋盤上所有64格的麥粒，都賞給您的仆人吧！”國王覺得這個要求太容易滿足了，就指令給他這些麥粒。當人們把一袋一袋的麥子搬來開始計數時，國王才發現：就是把全印度甚至全世界的麥粒全拿來，也滿足不了那位宰相的要求。

那麼，宰相要求得到的麥粒到底有多少呢？總數為

1+2+2^2 + … +2^63=2^64-1

等于移完漢諾塔所需的步驟數。我們已經知道這個數字有多麼大了。人們估計，全世界兩千年也難以生産這麼多麥子！