移動盤子演算法
㈠ 漢諾塔遞歸演算法是什麼
如下：
1、漢諾塔（又稱河內塔）問題是源於印度一個古老傳說的益智玩具。大梵天創造世界的時候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤。
大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。並且規定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動一個圓盤。
2、抽象為數學問題：從左到右有A、B、C三根柱子，其中A柱子上面有從小疊到大的n個圓盤，現要求將A柱子上的圓盤移到C柱子上去，期間只有一個原則：一次只能移到一個盤子且大盤子不能在小盤子上面，求移動的步驟和移動的次數。
演算法分析（遞歸演算法）：
實現這個演算法可以簡單分為三個步驟：把n-1個盤子由A 移到 B；把第n個盤子由 A移到 C；把n-1個盤子由B 移到 C。從這里入手，在加上上面數學問題解法的分析，我們不難發現，移到的步數必定為奇數步。
1、中間的一步是把最大的一個盤子由A移到C上去。
2、中間一步之上可以看成把A上n-1個盤子通過藉助輔助塔（C塔）移到了B上。
3、中間一步之下可以看成把B上n-1個盤子通過藉助輔助塔（A塔）移到了C上。
㈡ 移動n個盤子的演算法
這個次數本來就是按照移動規則的最小值,用歸納法即可證明的
別的移動方法只可能會增多
㈢ 在C語言中用函數編寫漢諾塔
*問題分析與演算法設計
這是一個著名的問題，幾乎所有的教材上都有這個問題。由於條件是一次只能移動一個盤，且不允許大盤放在小盤上面，所以64個盤的移動次數是：
18，446，744，073，709，551，615
這是一個天文數字，若每一微秒可能計算(並不輸出)一次移動，那麼也需要幾乎一百萬年。我們僅能找出問題的解決方法並解決較小N值時的漢諾塔，但很難用計算機解決64層的漢諾塔。
分析問題，找出移動盤子的正確演算法。
首先考慮a桿下面的盤子而非桿上最上面的盤子，於是任務變成了：
*將上面的63個盤子移到b桿上；
*將a桿上剩下的盤子移到c桿上；
*將b桿上的全部盤子移到c桿上。
將這個過程繼續下去，就是要先完成移動63個盤子、62個盤子、61個盤子....的工作。
為了更清楚地描述演算法，可以定義一個函數movedisc(n,a,b,c)。該函數的功能是：將N個盤子從A桿上藉助C桿移動到B桿上。這樣移動N個盤子的工作就可以按照以下過程進行：
1) movedisc(n-1,a,c,b);
2) 將一個盤子從a移動到b上；
3) movedisc(n-1,c,b,a)；
重復以上過程，直到將全部的盤子移動到位時為止。
*程序與程序注釋
#include<stdio.h>
void movedisc(unsigned n,char fromneedle,char toneedle,char usingneedle);
int i=0;
void main()
{
unsigned n;
printf("please enter the number of disc:");
scanf("%d",&n); /*輸入N值*/
printf("\tneedle:\ta\t b\t c\n");
movedisc(n,'a','c','b'); /*從A上藉助B將N個盤子移動到C上*/
printf("\t Total: %d\n",i);
}
void movedisc(unsigned n,char fromneedle,char toneedle,char usingneedle)
{
if(n>0)
{
movedisc(n-1,fromneedle,usingneedle,toneedle);
/*從fromneedle上藉助toneedle將N-1個盤子移動到usingneedle上*/
++i;
switch(fromneedle) /*將fromneedle 上的一個盤子移到toneedle上*/
{
case 'a': switch(toneedle)
{
case 'b': printf("\t[%d]:\t%2d.........>%2d\n",i,n,n);
break;
case 'c': printf("\t[%d]:\t%2d...............>%2d\n",i,n,n);
break;
}
break;
case 'b': switch(toneedle)
{
case 'a': printf("\t[%d]:\t%2d<...............>%2d\n",i,n,n);
break;
case 'c': printf("\t[%d]:\t %2d........>%2d\n",i,n,n);
break;
}
break;
case 'c': switch(toneedle)
{
case 'a': printf("\t[%d]:\t%2d<............%2d\n",i,n,n);
break;
case 'b': printf("\t[%d]:\t%2d<........%2d\n",i,n,n);
break;
}
break;
}
movedisc(n-1,usingneedle,toneedle,fromneedle);
/*從usingneedle上藉助fromneedle將N-1個盤子移動到toneedle上*/
}
}
㈣ 漢諾塔的演算法
演算法介紹：當盤子的個數為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
漢諾塔問題也是程序設計中的經典遞歸問題。
(4)移動盤子演算法擴展閱讀
由來：
法國數學家愛德華·盧卡斯曾編寫過一個印度的古老傳說：在世界中心貝拿勒斯（在印度北部）的聖廟里，一塊黃銅板上插著三根寶石針。印度教的主神梵天在創造世界的時候，在其中一根針上從下到上地穿好了由大到小的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億年，不說太陽系和銀河系，至少地球上的一切生命，連同梵塔、廟宇等，都早已經灰飛煙滅。