![漢諾塔[益智玩具]](/img/e/58c/nBnauM3X4EDMyATO5ETM5EDN0UTMyITNykTO0EDMwAjMwUzLxEzLxQzLt92YucmbvRWdo5Cd0FmLyE2LvoDc0RHa.jpg "漢諾塔[益智玩具]")
由來及傳說
由來
法國數學家愛德華·盧卡斯曾編寫過一個印度的古老傳說：在世界中心貝拿勒斯（在印度北部）的聖廟裡，一塊黃銅板上插著三根寶石針。印度教的主神梵天在創造世界的時候，在其中一根針上從下到上地穿好了由大到小的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
等於移完漢諾塔所需的步驟數。我們已經知道這個數字有多么大了。人們估計，全世界兩千年也難以生產這么多麥子！
相關預言
有預言說，這件事完成時宇宙會在一瞬間閃電式毀滅。也有人相信婆羅門至今還在一刻不停地搬動著圓盤。
其他相關
宇宙壽命
如果移動一個圓盤需要1秒鐘的話，等到64個圓盤全部重新落在一起，宇宙被毀滅是什麼時候呢？
讓我們來考慮一下64個圓盤重新摞好需要移動多少次吧。1個的時候當然是1次，2個的時候是3次，3個的時候就用了7次......這實在是太累了
因此讓我們邏輯性的思考一下吧。
3個的時候能夠移動最大的3盤時如圖所示。
![漢諾塔[益智玩具]](/img/a/9da/wZwpmLzcjM2YDN3YTN1ATN0UTMyITNykTO0EDMwAjMwUzL2UzL0EzLt92YucmbvRWdo5Cd0FmLyE2LvoDc0RHa.jpg)
漢諾塔[益智玩具]到此為止用了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
漢諾塔問題也是程式設計中的經典遞歸問題，下面我們將給出遞歸和非遞歸的不同實現原始碼。
程式實現
Python
C語言
FORTRAN
漢諾塔問題的非遞歸實現
漢諾塔遞歸
C#
Java
php
簡單的用php實現了漢諾塔問題的求解，使用遞歸調用，但是用php實現要是盤子的個數很多的話，運行起來會很慢的...
漢諾塔主要是有三個塔座X，Y，Z，要求將三個大小不同，依小到大編號為1，2.....n的圓盤從A移動到塔座Z上，要求
（1）：每次只能移動一個圓盤
（2）：圓盤可以插到X，Y，Z中任一塔座上
（3）：任何時候不能將一個較大的圓盤壓在較小的圓盤之上
主要是運用了遞歸的思想，這裡使用php做個簡單的實現......
pascal
Lua
易語言
子程式 漢諾塔盤子運動
.參數 盤子數，整數型
.參數 柱子甲，文本型
.參數 柱子乙，文本型
.參數 柱子丙，文本型
.如果 （盤子數 = 1）
' 如果只有一個盤，則直接將它從柱子一移動到柱子三
移動 （1，柱子甲，柱子丙）
.否則
' 把1 ~ n - 1個盤從柱子一移動到柱子二，用柱子三作為中轉
漢諾塔盤子運動 （盤子數 － 1，柱子甲，柱子丙，柱子乙）
' 把第n個盤從柱子一移動到柱子三
移動 （盤子數，柱子甲，柱子丙）
' 把1 ~ n - 1個盤從柱子二移動到柱子三，用柱子一作為中轉
漢諾塔盤子運動 （盤子數 － 1，柱子乙，柱子甲，柱子丙）
.如果結束
.子程式 移動
.參數 盤子號，整數型
.參數 甲柱子，文本型
.參數 乙柱子，文本型
路徑 = 路徑 + “步驟” + 到文本 （步驟） + “：” + “把” + 到文本 （盤子號） + “號圓盤從柱子 ” + 甲柱子 + “ 移動到” + 乙柱子 + “上 ” + #換行符
步驟 = 步驟 + 1
.子程式 _計算圖形按鈕_被單擊
.局部變數 盤子總數，整數型
.局部變數 現在柱子，文本型
易語言--hanoi.局部變數 中間柱子，文本型
.局部變數 目標柱子，文本型
' 把盤子編輯框.內容傳給現在柱子
現在柱子 = 盤子編輯框.內容
' 把中間編輯框.內容傳給中間柱子
中間柱子 = 中間編輯框.內容
' 把目標編輯框.內容傳給目標柱子
目標柱子 = 目標編輯框.內容
.如果真 （到數值 （現在柱子） ≤ 0 或 到數值 （中間柱子） ≤ 0 或 到數值 （目標柱子） ≤ 0 或 到數值 （個數編輯框.內容） ≤ 0 或 到數值 （個數編輯框.內容） > 10）
信息框 （“柱子或圓盤數量只能是大於0小於10的數字！”，#錯誤圖示，“出現錯誤了：”）
返回 ()
.如果真結束
盤子總數 = 到數值 （個數編輯框.內容）
結果編輯框.內容 = “”
路徑 = “”
' 首次調用漢諾塔盤子運動 （）程式
漢諾塔盤子運動 （盤子總數，現在柱子，中間柱子，目標柱子）
結果編輯框.內容 = 路徑
步驟 = 1
