c漢諾塔演算法
#include#define MAXSTACK 10 /* 棧的最大深度 */int c = 1; /* 一個全局變數，表示目前移動的步數 */struct hanoi { /* 存儲漢諾塔的結構，包括盤的數目和三個盤的名稱 */
int n;
char x, y, z;
};void move(char x, int n, char y) /* 移動函數，表示把某個盤從某根針移動到另一根針 */
{
printf("%d. Move disk %d from %c to %cn", c++, n, x, y);
}void hanoi(int n, char x, char y, char z) /* 漢諾塔的遞歸演算法 */
{
if (1 == n)
move(x, 1, z);
else {
hanoi(n - 1, x, z, y);
move(x, n, z);
hanoi(n - 1, y, x, z);
}
}void push(struct hanoi *p, int top, char x, char y, char z,int n)
{
p[top+1].n = n - 1;
p[top+1].x = x;
p[top+1].y = y;
p[top+1].z = z;
}void unreverse_hanoi(struct hanoi *p) /* 漢諾塔的非遞歸演算法 */
{
int top = 0;while (top >= 0) {
while (p[top].n > 1) { /* 向左走到盡頭 */
push(p, top, p[top].x, p[top].z, p[top].y, p[top].n);
top++;
}
if (p[top].n == 1) { /* 葉子結點 */
move(p[top].x, 1, p[top].z);
top--;
}
if (top >= 0) { /* 向右走一步 */
move(p[top].x, p[top].n, p[top].z);
top--;
push(p, top, p[top+1].y, p[top+1].x, p[top+1].z, p[top+1].n);
top++;
}
}
}int main(void)
{
int i;
printf("reverse program:n");
hanoi(3, 'x', 'y', 'z');
printf("unreverse program:n");
struct hanoi p[MAXSTACK];
c = 1;
p[0].n = 3;
p[0].x = 'x', p[0].y = 'y', p[0].z = 'z';
unreverse_hanoi(p);return 0;
}
2. 漢諾塔怎麼玩
一位美國學者發現的特別簡單的方法：只要輪流用兩次如下方法就可以了。
把三根柱子按順序排成「品」字型，把所有圓盤按從大到小的順序放於柱子A上，根據圓盤數量來確定柱子排放的順序：
n若為偶數的話，順時針方向依次擺放為：ABC；而n若為奇數的話，就按順時針方向依次擺放為：ACB。這樣經過反復多次的測試，最後就可以按照規定完成漢諾塔的移動。
因此很簡單的，結果就是按照移動規則向一個方向移動金片：
如3階漢諾塔的移動：A→C，A→B，C→B，A→C，B→A，B→C，A→C。
(2)c漢諾塔演算法擴展閱讀：
由來
法國數學家愛德華·盧卡斯曾編寫過一個印度的古老傳說：在世界中心貝拿勒斯（在印度北部）的聖廟里，一塊黃銅板上插著三根寶石針。印度教的主神梵天在創造世界的時候，在其中一根針上從下到上地穿好了由大到小的64片金片，這就是所謂的漢諾塔。
不論白天黑夜，總有一個僧侶在按照下面的法則移動這些金片：一次只移動一片，不管在哪根針上，小片必須在大片上面。僧侶們預言，當所有的金片都從梵天穿好的那根針上移到另外一根針上時，世界就將在一聲霹靂中消滅，而梵塔、廟宇和眾生也都將同歸於盡。
3. 漢諾塔遞歸演算法是什麼
hanot (n-1,b,a,c);（解釋：在把B塔上的(n-1))個藉助A塔移動到C塔）
為了實現 n個盤從 藉助c 從a 移動到 b
思路如下：
首先考慮極限當只有一個盤的時候，盤直接從 a -> b即可。
當有2個盤的時候，把1號盤從a -> c 然後 把2號盤 a->b 再 把 2好盤從 c - > b。
當有n個盤的時候，把 n-1個 盤 藉助 b 移動到 c 然後將 n號盤從 a -> b。
這時候只要將 n-1想辦法從c移動到 b 藉助 a 那麼就可以先把 n-2個盤藉助b移動到a。
遞歸，就是在運行的過程中調用自己。
構成遞歸需具備的條件：
1，子問題須與原始問題為同樣的事，且更為簡單；
2，不能無限制地調用本身，須有個出口，化簡為非遞歸狀況處理。
在數學和計算機科學中，遞歸指由一種（或多種）簡單的基本情況定義的一類對象或方法，並規定其他所有情況都能被還原為其基本情況。
以上內容參考：網路-遞歸公式
4. 漢諾塔怎麼玩的
漢諾塔規律總結口訣是單左雙右，先小後大，一步兩步，循環往復。
設3個柱子分別是甲，乙，丙，把3根柱子看成一個循環，也就是說，甲的右邊是乙，乙的右邊是丙，而丙的右邊則回到甲，同理，甲的左邊就是丙。簡單點，記住丙的右邊是甲，和甲的左邊是丙就行了。盤子分別是盤1，盤2，盤3，盤4……盤1最小。按照「單左雙右」的規律，先移動小的，也就是先移動盤1，再移動盤2，盤3，按順序，把能移動的都移動一次，每次移動一步，如果不符合游戲規則，就移動兩步，還是不符合的話，就找到盤1，重新按照「單左雙右」的規則走，直到完成游戲。
漢諾塔公式：
現在有三根相鄰的柱子，標號為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)。
5. C語言漢諾塔問題，請問這個n=3的詳細步驟是什麼呀，大一新生沒聽懂
這是漢諾塔的演算法的問題。程序本身很簡單。
漢諾塔（又稱河內塔）問題是源於印度一個古老傳說的益智玩具。大梵天創造世界的時候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤。大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。並且規定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動一個圓盤。
這個主要是看演算法，再一個就是遞歸的學習，程序本身非常簡單。
6. C語言--漢諾塔程序執行步驟
這個問題你要先把遞歸搞懂才能理解的, 最好是單跟蹤執行一下, 我這里就簡單說一下吧!
hanoi(5, 'a', 'b', 'c');把5個從'a'移到'c'
這時n=5, noe='a', two='b', three='c'
因為n!=1, 執行else里的
hanoi( 4, 'a', 'c', 'b'); //把上面4個從a移到b
move( 'a', 'c'); //把第5個從a移到c
hanoi( 4, 'b', 'a', 'c'); //再把那4個從b移到c
上面的很好明白的, 再分析hanoi( 4, 'a', 'c', 'b'); //把上面4個從a移到b,也是執行else
hanoi( 3, 'a', 'b', 'c'); //把上面3個從a移到c
move( 'a', 'b'); //把第4個從a移到b
hanoi( 4, 'c', 'a', 'b'); //再把那3個從c移到b
一直到n=1才結束
7. 漢諾塔問題公式是什麼
漢諾塔問題（又稱河內塔問題）是根據一個傳說形成的一個問題：
有三根桿子A，B，C。A桿上有N個(N>1)穿孔圓盤，盤的尺寸由下到上依次變小。要求按下列規則將所有圓盤移至C桿：
1. 每次只能移動一個圓盤；
2. 大盤不能疊在小盤上面。
提示：可將圓盤臨時置於B桿，也可將從A桿移出的圓盤重新移回A桿，但都必須尊循上述兩條規則。
問：如何移？最少要移動多少次？
一般取N=64。這樣，最少需移動264-1次。即如果一秒鍾能移動一塊圓盤，仍將需5845.54億年。目前按照宇宙大爆炸理論的推測，宇宙的年齡僅為137億年。
在真實玩具中，一般N=8；這將需移動255次。如果N=10，需移動1023次。如果N=15，需移動32767次；這就是說，如果一個人從3歲到99歲，每天移動一塊圓盤，他僅能移動15塊。如果N=20，需移動1048575次，即超過了一百萬次。
先看hanoi(1, one, two, three)的情況。這時直接將one柱上的一個盤子搬到three柱上。注意，這里one柱或three柱到底是A、B還是C並不重要，要記住的是函數第二個參數代表的柱上的一個盤被搬到第四個參數代表的柱上。為方便，將這個動作記為：
one =》three
再看hanoi(2, one, two, three)的情況。考慮到hanoi(1)的情況已經分析過了，可知這時實際上將產生三個動作，分別是：
one =》two
one =》three
two =》three
很顯然，這實際上相當於將one柱上的兩個盤直接搬到three柱上。
再看hanoi(3, one, two, three)的情況。分析
hanoi(2, one , three, two)
one =》three
hanoi(2, two, one, three)
即：先將one柱上的兩個盤搬到two柱上，再將one柱上的一個盤搬到three柱上，最後再將two柱上的兩個盤搬到three柱上。這不就等於將one柱上的三個盤直接搬到three柱上嗎？
運用歸納法可知，對任意n，
hanoi(n-1, one , three, two)
one =》three
hanoi(n-1, two, one, three)
就是先將one柱上的n-1個盤搬到two柱上，再將one柱上的一個盤搬到three柱上，最後再將two柱上的n-1個盤搬到three柱上。這就是我們所需要的結果！
回答者：wuchenghua121 - 經理 四級 12-5 11:51
漢諾塔
漢諾塔（又稱河內塔）問題是印度的一個古老的傳說。開天闢地的神勃拉瑪在一個廟里留下了三根金剛石的棒，第一根上面套著64個圓的金片，最大的一個在底下，其餘一個比一個小，依次疊上去，廟里的眾僧不倦地把它們一個個地從這根棒搬到另一根棒上，規定可利用中間的一根棒作為幫助，但每次只能搬一個，而且大的不能放在小的上面。解答結果請自己運行計算，程序見尾部。面對龐大的數字(移動圓片的次數)18446744073709551615，看來，眾僧們耗盡畢生精力也不可能完成金片的移動。
後來，這個傳說就演變為漢諾塔游戲:
1.有三根桿子A,B,C。A桿上有若干碟子
2.每次移動一塊碟子,小的只能疊在大的上面
3.把所有碟子從A桿全部移到C桿上
經過研究發現，漢諾塔的破解很簡單，就是按照移動規則向一個方向移動金片：
如3階漢諾塔的移動：A→C,A→B,C→B,A→C,B→A,B→C,A→C
此外，漢諾塔問題也是程序設計中的經典遞歸問題。
補充：漢諾塔的演算法實現（c++）
#include <fstream>
#include <iostream>
using namespace std;
ofstream fout("out.txt");
void Move(int n,char x,char y)
{
fout<<"把"<<n<<"號從"<<x<<"挪動到"<<y<<endl;
}
void Hannoi(int n,char a,char b,char c)
{
if(n==1)
Move(1,a,c);
else
{
Hannoi(n-1,a,c,b);
Move(n,a,c);
Hannoi(n-1,b,a,c);
}
}
int main()
{
fout<<"以下是7層漢諾塔的解法:"<<endl;
Hannoi(7,'a','b','c');
fout.close();
cout<<"輸出完畢！"<<endl;
return 0;
}
C語言精簡演算法
/* Copyrighter by SS7E */
#include<stdio.h> /* Copyrighter by SS7E */
void hanoi(int n,char A,char B,char C) /* Copyrighter by SS7E */
{
if(n==1)
{
printf("Move disk %d from %c to %c\n",n,A,C);
}
else
{
hanoi(n-1,A,C,B); /* Copyrighter by SS7E */
printf("Move disk %d from %c to %c\n",n,A,C);
hanoi(n-1,B,A,C); /* Copyrighter by SS7E */
}
}
main() /* Copyrighter by SS7E */
{
int n;
printf("請輸入數字n以解決n階漢諾塔問題：\n");
scanf("%d",&n);
hanoi(n,'A','B','C');
}/* Copyrighter by SS7E */
回答者： Vanquisher_ - 舉人 五級 12-5 13:57
parcel::::::::::
program hanoi;
functionhanoi(x:integer):longint;
begin
if x=1 then hanoi:=1;
if x=2 then hanoi:=3;
else
begin
hanoi:=2*hanoi(x-1)+1;
end;
end;
begin
read(x){第幾個數 }
write(hanoi(x));
end.
思想就是：第N個就等於第n-1個乘以2+1次
8. c語言用遞歸實現漢諾塔
見代碼注釋，還有不懂可以問。
#include<stdio.h>
voidmove(charx,chary)
{
printf("%c-->%c ",x,y);
}
//hannuota函數的作用：把n個圓盤從one柱子藉助two柱子放到three柱子
voidhannuota(intn,charone,chartwo,charthree)
{
if(n==1)//如果只有一個柱子
move(one,three);//直接移動即可
else
{
hannuota(n-1,one,three,two);//先把one柱子上的n-1個圓盤藉助three柱子移動到柱子two
move(one,three);//把第一個柱子的剩下那一個(第n個)移動到第三個柱子
//由於原來one柱子上的n-1個圓盤已經移動到了two柱子上，因此不會有圓盤擋住n圓盤出來
hannuota(n-1,two,one,three);
//最後再把那n-1個圓盤從two柱子藉助one柱子移動到three柱子
//(上面第一句話hannuota(n-1,one,three,two)已經移動到了two柱子，因此這里是從two柱子移動到three柱子)
}
}
intmain()
{
intm;
printf("inputthenumberofdiskes:");
scanf("%d",&m);
printf("Thesteptomove%ddiskes: ",m);
hannuota(m,'A','B','C');
return0;
}
9. C語言漢諾塔程序
將以下內容全部復制到新建的源文件中：（本人自己寫的，因為你那課本上的代碼，沒解釋，書寫不規范，很難理解清楚，所以我直接新寫了一個完整的代碼，附帶詳細說明）
#include <stdio.h>
//漢諾塔x層塔從A塔整體搬到C塔，中間臨時B塔。
//x層塔是從大到小往上疊放。每次移動只能移動一層塔。並且在移動過程中必須保證小層在上邊
//藉助B塔可以將x層塔全部從A搬到C上，並且符合要求（在移動過程中大的那塊在下邊，小的那塊在上邊）
int main()
{
void tower(int x,char a,char b,char c); //聲明函數
int x=5,a='A',b='B',c='C'; //x表示有5層塔，具體要多少層自己修改這個值。abc分別表示ABC塔。
tower(x,a,b,c); //x層塔從a移動到c的全過程，主程序只有這條有效語句
return 0;
}
//以下是tower函數的定義
//參數解析：x層塔放在a上，b是中間塔，c是目標塔。即x層塔要從a搬到c上。
//此函數實現x層塔從a整體轉移到c上。以及這個過程是怎麼搬的全部過程。
void tower(int x,char a,char b,char c)
{
if(x==1)printf("將%d從%c放到%c\n",x,a,c); //只有1層塔時，直接從a搬到c上。
else //不止1層塔，則先將x-1層塔從a按照規律搬到b上，再將最後一塊從a搬到c上，最後再將b上的x-1層塔按照規律搬到c上。
{
tower(x-1,a,c,b); //先將x-1層塔從a按照規律搬到b上，注意參數b放在最後，因為放在最後的參數是准備搬過去的目標塔。
printf("將%d從%c放到%c\n",x,a,c); //將最後一塊從a搬到c上
tower(x-1,b,a,c); //最後再將b上的x-1層塔按照規律搬到c上，注意參數b放在開頭，因為x-1層是要從b上搬過去的。
}
}