概述
有三根杆子A，B，C。A杆上有N個(N>1)穿孔圓盤，盤的尺寸由下到上依次變小。要求按下列規則将所有圓盤移至C杆： 每次隻能移動一個圓盤； 大盤不能疊在小盤上面。 提示：可将圓盤臨時置于B杆，也可将從A杆移出的圓盤重新移回A杆，但都必須遵循上述兩條規則。
由來及傳說
由來
法國數學家愛德華·盧卡斯曾編寫過一個印度的古老傳說：在世界中心貝拿勒斯（在印度北部）的聖廟裡，一塊黃銅闆上插着三根寶石針。印度教的主神梵天在創造世界的時候，在其中一根針上從下到上地穿好了由大到小的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億年，不說太陽系和銀河系，至少地球上的一切生命，連同梵塔、廟宇等，都早已經灰飛煙滅。
印度傳說
和漢諾塔故事相似的，還有另外一個印度傳說：舍罕王打算獎賞國際象棋的發明人──宰相西薩·班·達依爾。國王問他想要什麼，他對國王說：“陛下，請您在這張棋盤的第1個小格裡賞給我一粒麥子，在第2個小格裡給2粒，第3個小格給4粒，以後每一小格都比前一小格加一倍。請您把這樣擺滿棋盤上所有64格的麥粒，都賞給您的仆人吧！”國王覺得這個要求太容易滿足了，就命令給他這些麥粒。當人們把一袋一袋的麥子搬來開始計數時，國王才發現：就是把全印度甚至全世界的麥粒全拿來，也滿足不了那位宰相的要求。
那麼，宰相要求得到的麥粒到底有多少呢？總數為
1+2+2^2 + … +2^63=2^64-1
等于移完漢諾塔的步驟數——共3853步。我們已經知道這個數字有多麼大了。人們估計，全世界兩千年也難以生産這麼多麥子！
相關預言
有預言說，這件事完成時宇宙會在一瞬間閃電式毀滅。也有人相信婆羅門至今還在一刻不停地搬動着圓盤。
其他相關
與宇宙壽命
如果移動一個圓盤需要1秒鐘的話，等到64個圓盤全部重新落在一起，宇宙被毀滅是什麼時候呢？
讓我們來考慮一下64個圓盤重新摞好需要移動多少次吧。1個的時候當然是1次，2個的時候是3次，3個的時候就用了7次......這實在是太累了因此讓我們邏輯性的思考一下吧。3個的時候能夠移動最大的3盤時如圖所示。到此為止用了7次。
接下來如右圖，在上面再放上3個圓盤時還要用7次（把3個圓盤重新放在一起需要的次數）。因此，4個的時候是“3個圓盤重新摞在一起的次數”+1次+“3個圓盤重新摞在一起需要的次數”=2x“3個圓盤重新摞在一起的次數”+1次=15次。
那麼，n個的時候是2x“（n-1）個圓盤重新摞在一起的次數”+1次。由于1 個的時候是1次，結果n個的時候為（2的n次方減1）次。
1個圓盤的時候 2的1次方減1
2個圓盤的時候 2的2次方減1
3個圓盤的時候 2的3次方減1
4個圓盤的時候 2的4次方減1
5個圓盤的時候 2的5次方減1
........
n個圓盤的時候 2的n次方減1
也就是說，n=64的時候是（2的64次方減1）次。
因此，如果移動一個圓盤需要1秒的話，
宇宙的壽命=2的64次方減1（秒）
2的64次方減1到底有多大呢？動動計算器，答案是一個二十位的數字約是
1.84467440*10^19
用一年=60秒x60分x24小時x365天來算的話，大約有5800億年吧。
太陽及其行星形成于50億年前，其壽命約為100億年。
漢諾塔問題在數學界有很高的研究價值，而且至今還在被一些數學家們所研究。
也是我們所喜歡玩的一種益智遊戲，它可以幫助開發智力，激發我們的思維。
經典題目
有三根相鄰的柱子，标号為A,B,C，A柱子上從下到上按金字塔狀疊放着n個不同大小的圓盤，要把所有盤子一個一個移動到柱子B上，并且每次移動同一根柱子上都不能出現大盤子在小盤子上方，請問至少需要多少次移動，設移動次數為H(n）。
首先我們肯定是把上面n-1個盤子移動到柱子C上，然後把最大的一塊放在B上，最後把C上的所有盤子移動到B上，由此我們得出表達式：
H⑴ = 1
H(n) = 2*H(n-1）+1 (n>1）
那麼我們很快就能得到H(n）的一般式：
H(n) = 2^n - 1 (n>0)
并且這種方法的确是最少次數的，證明非常簡單，可以嘗試從2個盤子的移動開始證，你可以試試。
進一步加深問題（解法原創*_*）：
假如現在每種大小的盤子都有兩個，并且是相鄰的，設盤子個數為2n，問：⑴假如不考慮相同大小盤子的上下要多少次移動，設移動次數為J(n）；⑵隻要保證到最後B上的相同大小盤子順序與A上時相同，需要多少次移動，設移動次數為K(n）。
⑴中的移動相當于是把前一個問題中的每個盤子多移動一次，也就是：
J(n) = 2*H(n) = 2*（2^n - 1） = 2^(n+1）-2
在分析⑵之前
，我們來說明一個現象，假如A柱子上有兩個大小相同的盤子，上面一個是黑色的，下面一個是白色的，我們把兩個盤子移動到B上，需要兩次，盤子順序将變成黑的在下，白的在上，然後再把B上的盤子移動到C上，需要兩次，盤子順序将與A上時相同，由此我們歸納出當相鄰兩個盤子都移動偶數次時，盤子順序将不變，否則上下颠倒。
現在回到最開始的問題，n個盤子移動，上方的n-1個盤子總移動次數為2*H(n-1），所以上方n-1個盤子的移動次數必定為偶數次，最後一個盤子移動次數為1次。
讨論問題⑵，
綜上兩點，可以得出，要把A上2n個盤子移動到B上，首先可以得出上方的2n-2個盤子必定移動偶數次，所以順序不變，移動次數為：
J(n-1） = 2^n-2
然後再移動倒數第二個盤子，移動次數為2*J(n-1）+1 = 2^(n+1）-3，
最後移動最底下一個盤子，所以總的移動次數為：
K(n) = 2*（2*J(n-1）+1）+1 = 2*（2^(n+1）-3）+1 = 2^(n+2）-5
開天辟地的神勃拉瑪（和中國的盤古差不多的神吧）在一個廟裡留下了三根金剛石的棒，第一根上面套着64個圓的金片，最大的一個在底下，其餘一個比一個小，依次疊上去，廟裡的衆僧不倦地把它們一個個地從這根棒搬到另一根棒上，規定可利用中間的一根棒作為幫助，但每次隻能搬一個，而且大的不能放在小的上面。計算結果非常恐怖（移動圓片的次數）大約是1.84467440*10^19，衆僧們即便是耗盡畢生精力也不可能完成金片的移動了。
算法介紹
其實算法非常簡單，當盤子的個數為n時，移動的次數應等于2^n – 1（有興趣的可以自己證明試試看）。後來一位美國學者發現一種出人意料的簡單方法，隻要輪流進行兩步操作就可以了。首先把三根柱子按順序排成品字型，把所有的圓盤按從大到小的順序放在柱子A上，根據圓盤的數量确定柱子的排放順序：若n為偶數，按順時針方向依次擺放 A B C；
若n為奇數，按順時針方向依次擺放 A C B。
⑴按順時針方向把圓盤1從現在的柱子移動到下一根柱子，即當n為偶數時，若圓盤1在柱子A，則把它移動到B；若圓盤1在柱子B，則把它移動到C；若圓盤1在柱子C，則把它移動到A。
⑵接着，把另外兩根柱子上可以移動的圓盤移動到新的柱子上。即把非空柱子上的圓盤移動到空柱子上，當兩根柱子都非空時，移動較小的圓盤。這一步沒有明确規定移動哪個圓盤，你可能以為會有多種可能性，其實不然，可實施的行動是唯一的。
⑶反複進行⑴⑵操作，最後就能按規定完成漢諾塔的移動。
所以結果非常簡單，就是按照移動規則向一個方向移動金片：
如3階漢諾塔的移動：A→C,A→B,C→B,A→C,B→A,B→C,A→C。
