漢諾塔編程

① 漢諾塔的演算法

演算法介紹：當盤子的個數為n時，移動的次數應等於2^n–1。後來一位美國學者發現一種出人意料的簡單方法，只要輪流進行兩步操作就可以了。首先把三根柱子按順序排成品字型，把所有的圓盤按從大到小的順序放在柱子A上，根據圓盤的數量確定柱子的排放順序：若n為偶數，按順時針方向依次擺放A、B、C；

若n為奇數，按順時針方向依次擺放A、C、B。

所以結果非常簡單，就是按照移動規則向一個方向移動金片：如3階漢諾塔的移動：A→C,A→B,C→B,A→C,B→A,B→C,A→C

漢諾塔問題也是程序設計中的經典遞歸問題。

(1)漢諾塔編程擴展閱讀

由來：

法國數學家愛德華·盧卡斯曾編寫過一個印度的古老傳說：在世界中心貝拿勒斯（在印度北部）的聖廟里，一塊黃銅板上插著三根寶石針。印度教的主神梵天在創造世界的時候，在其中一根針上從下到上地穿好了由大到小的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億年，不說太陽系和銀河系，至少地球上的一切生命，連同梵塔、廟宇等，都早已經灰飛煙滅。

② C++ 奇怪的雙色漢諾塔問題

這和普通的漢諾塔問題是相同的。為什麼呢？

考察一個普通的漢諾塔問題，如果按照最少步驟移動（即沒有無意義的移來移去）：

普通的漢諾塔（把盤子1~k由source移動到target）問題分三個階段
1.把盤子1~k-1由source（k上面）移動到assistant
2.把盤子k由source移動到target
3.把盤子1~k-1由assistant移動到target（k上面）
在這里我們把盤子1~k-1的移動看做一個整體進行移動

那麼假設存在一個違反雙色規則移動的盤子m-1，它放在了盤子m+1上，但是你讓盤子m怎麼辦呢？在移動1~m+1這個層次並沒有盤子m在m+1所在柱子之外的兩個柱子間移動的步驟。
m-1放在m+3、m+5、m+7……之上也是不可能的，因為同樣地，就拿m+3來說，在移動1~m+3這個層次沒有盤子m+2在m+3所在柱子之外的兩個柱子間移動的步驟。

所以這種違規必然是一個多餘的操作，違規地移動之後，必須要移下來才能正常繼續。

至於普通的漢諾塔問題如何解決，你大可搜到答案無需我講了吧。

③ 如何做一個C語言編程的漢諾塔游戲

#includex0dx0a void move(char x,char y)x0dx0a {x0dx0a printf("%c-->%c\n",x,y);x0dx0a }x0dx0a void hanoi(int n,char one ,char two,char three)x0dx0a {x0dx0a if(n==1) move(one,three);x0dx0a elsex0dx0a {x0dx0a hanoi(n-1,one,three,two);x0dx0a move(one,three);x0dx0a hanoi(n-1,two,one,three);x0dx0a }x0dx0a }x0dx0a main()x0dx0a {x0dx0a int m;x0dx0a printf("input the number of disks:");x0dx0a scanf("%d",&m);x0dx0a printf("the step to moving %3d diskes:\n",m);x0dx0a hanoi(m,'A','B','C');x0dx0a }x0dx0a演算法介紹：x0dx0a 其實演算法非常簡單，當盤子的個數為n時，移動的次數應等於2^n _ 1（有興趣的可以自己證明試試看）。後來一位美國學者發現一種出人意料的簡單方法，只要輪流進行兩步操作就可以了。首先把三根柱子按順序排成品字型，把所有的圓盤按從大到小的順序放在柱子A上，根據圓盤的數量確定柱子的排放順序：若n為偶數，按順時針方向依次擺放 A B C；x0dx0a 若n為奇數，按順時針方向依次擺放 A C B。x0dx0a （1）按順時針方向把圓盤1從現在的柱子移動到下一根柱子，即當n為偶數時，若圓盤1在柱子A，則把它移動到B；若圓盤1在柱子B，則把它移動到C；若圓盤1在柱子C，則把它移動到A。x0dx0a （2）接著，把另外兩根柱子上可以移動的圓盤移動到新的柱子上。即把非空柱子上的圓盤移動到空柱子上，當兩根柱子都非空時，移動較小的圓盤。這一步沒有明確規定移動哪個圓盤，你可能以為會有多種可能性，其實不然，可實施的行動是唯一的。x0dx0a （3）反復進行（1）（2）操作，最後就能按規定完成漢諾塔的移動。x0dx0a 所以結果非常簡單，就是按照移動規則向一個方向移動金片：x0dx0a 如3階漢諾塔的移動：A→C,A→B,C→B,A→C,B→A,B→C,A→Cx0dx0a 漢諾塔問題也是程序設計中的經典遞歸問題，下面我們將給出遞歸和非遞歸的不同實現源代碼。