c語言漢諾塔演算法

1. C璇璦瀹為獙棰樷斺旀眽璇哄

銆愪緥銆慔anoi濉旈棶棰
涓鍧楁澘涓婃湁涓夋牴閽堬紝A錛孊錛孋銆侫閽堜笂濂楁湁64涓澶у皬涓嶇瓑鐨勫渾鐩橈紝澶х殑鍦ㄤ笅錛屽皬鐨勫湪涓娿傚傚浘5.4鎵紺恆傝佹妸榪64涓鍦嗙洏浠嶢閽堢Щ鍔–閽堜笂錛屾瘡嬈″彧鑳界Щ鍔ㄤ竴涓鍦嗙洏錛岀Щ鍔ㄥ彲浠ュ熷姪B閽堣繘琛屻備絾鍦ㄤ換浣曟椂鍊欙紝浠諱綍閽堜笂鐨勫渾鐩橀兘蹇呴』淇濇寔澶х洏鍦ㄤ笅錛屽皬鐩樺湪涓娿傛眰縐誨姩鐨勬ラゃ
鏈棰樼畻娉曞垎鏋愬備笅錛岃続涓婃湁n涓鐩樺瓙銆
濡傛灉n=1錛屽垯灝嗗渾鐩樹粠A鐩存帴縐誨姩鍒癈銆
濡傛灉n=2錛屽垯錛
1.灝咥涓婄殑n-1(絳変簬1)涓鍦嗙洏縐誨埌B涓婏紱
2.鍐嶅皢A涓婄殑涓涓鍦嗙洏縐誨埌C涓婏紱
3.鏈鍚庡皢B涓婄殑n-1(絳変簬1)涓鍦嗙洏縐誨埌C涓娿
濡傛灉n=3錛屽垯錛
A. 灝咥涓婄殑n-1(絳変簬2錛屼護鍏朵負n`)涓鍦嗙洏縐誨埌B(鍊熷姪浜嶤)錛屾ラゅ備笅錛
(1)灝咥涓婄殑n`-1(絳変簬1)涓鍦嗙洏縐誨埌C涓娿
(2)灝咥涓婄殑涓涓鍦嗙洏縐誨埌B銆
(3)灝咰涓婄殑n`-1(絳変簬1)涓鍦嗙洏縐誨埌B銆
B. 灝咥涓婄殑涓涓鍦嗙洏縐誨埌C銆
C. 灝咮涓婄殑n-1(絳変簬2錛屼護鍏朵負n`)涓鍦嗙洏縐誨埌C(鍊熷姪A)錛屾ラゅ備笅錛
(1)灝咮涓婄殑n`-1(絳変簬1)涓鍦嗙洏縐誨埌A銆
(2)灝咮涓婄殑涓涓鐩樺瓙縐誨埌C銆
(3)灝咥涓婄殑n`-1(絳変簬1)涓鍦嗙洏縐誨埌C銆
鍒版わ紝瀹屾垚浜嗕笁涓鍦嗙洏鐨勭Щ鍔ㄨ繃紼嬨
浠庝笂闈㈠垎鏋愬彲浠ョ湅鍑猴紝褰搉澶т簬絳変簬2鏃訛紝縐誨姩鐨勮繃紼嬪彲鍒嗚В涓轟笁涓姝ラわ細
絎涓姝 鎶夾涓婄殑n-1涓鍦嗙洏縐誨埌B涓婏紱
絎浜屾 鎶夾涓婄殑涓涓鍦嗙洏縐誨埌C涓婏紱
絎涓夋 鎶夿涓婄殑n-1涓鍦嗙洏縐誨埌C涓婏紱鍏朵腑絎涓姝ュ拰絎涓夋ユ槸綾誨悓鐨勩
褰搉=3鏃訛紝絎涓姝ュ拰絎涓夋ュ張鍒嗚В涓虹被鍚岀殑涓夋ワ紝鍗蟲妸n`-1涓鍦嗙洏浠庝竴涓閽堢Щ鍒板彟涓涓閽堜笂錛岃繖閲岀殑n`=n-1銆 鏄劇劧榪欐槸涓涓閫掑綊榪囩▼錛屾嵁姝ょ畻娉曞彲緙栫▼濡備笅錛
move(int n,int x,int y,int z)
{
if(n==1)
printf("%c-->%c\n",x,z);
else
{
move(n-1,x,z,y);
printf("%c-->%c\n",x,z);
move(n-1,y,x,z);
}
}
main()
{
int h;
printf("\ninput number:\n");
scanf("%d",&h);
printf("the step to moving %2d diskes:\n",h);
move(h,'a','b','c');
}

浠庣▼搴忎腑鍙浠ョ湅鍑,move鍑芥暟鏄涓涓閫掑綊鍑芥暟錛屽畠鏈夊洓涓褰㈠弬n,x,y,z銆俷琛ㄧず鍦嗙洏鏁幫紝x,y,z鍒嗗埆琛ㄧず涓夋牴閽堛俶ove 鍑芥暟鐨勫姛鑳芥槸鎶妜涓婄殑n涓鍦嗙洏縐誨姩鍒皕涓娿傚綋n==1鏃訛紝鐩存帴鎶妜涓婄殑鍦嗙洏縐昏嚦z涓婏紝杈撳嚭x鈫抸銆傚俷!=1鍒欏垎涓轟笁姝ワ細閫掑綊璋冪敤move鍑芥暟錛屾妸n-1涓鍦嗙洏浠巟縐誨埌y錛涜緭鍑簒鈫抸錛涢掑綊璋冪敤move鍑芥暟錛屾妸n-1涓鍦嗙洏浠巠縐誨埌z銆傚湪閫掑綊璋冪敤榪囩▼涓璶=n-1錛屾晠n鐨勫奸愭￠掑噺錛屾渶鍚巒=1鏃訛紝緇堟㈤掑綊錛岄愬眰榪斿洖銆傚綋n=4 鏃剁▼搴忚繍琛岀殑緇撴灉涓猴細
input number:
4
the step to moving 4 diskes:
a鈫抌
a鈫抍
b鈫抍
a鈫抌
c鈫抋
c鈫抌
a鈫抌
a鈫抍
b鈫抍
b鈫抋
c鈫抋
b鈫抍
a鈫抌
a鈫抍
b鈫抍

2. 如何做一個C語言編程的漢諾塔游戲要有源代碼。

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

3. C璇璦奼夎哄旓紙楂樺垎鎻愰棶錛

hanio(n-1,a,c,b);錛堟彁闂錛氫負浠涔堝弬鏁拌劇疆涓篴,c,b錛
move(a,c);
hanio(n-1,b,a,c); (鎻愰棶錛氳岃繖涓鍙堣劇疆鎴愪負b,a,c)

鍏跺疄濡傛灉娓呮氫簡縐誨姩瑙勫垯,榪欎釜灝卞緢綆鍗曚簡.
鍒嗘瀽鏈変袱涓鐩樺瓙鐨勬儏鍐,鏄劇劧涓:
a-b
a-c
b-c
鍋囪炬湁n涓鐩樺瓙,鎴戜滑涔熷彲浠ョ湅浣滀袱涓鐩樺瓙,鍏朵腑鏈涓婇潰鐨勪竴涓涓簒,涓嬮潰鐨刵-1涓涓簓,閭ｄ箞榪欎袱涓鐩樺瓙鐨勪互鍚庡氨鍜屼笂闈涓鏍
x:a-b
y:a-c
x:b-c
鑰岄偅n-1涓鐩樺瓙涔熷彲浠ョ敤鍚屾牱鏂規硶澶勭悊.榪欐牱鎴戜滑鍍忔湁浜嗕竴涓鍏寮:
if(n==1)
鐩存帴灝嗕竴涓鐩樺瓙浠巃縐誨姩鍒癱;
else
{
鍏堝皢n-1涓鐩樺瓙浠巃縐誨姩鍒癰;
鎶婄琻涓鐩樺瓙浠巃縐誨姩鍒癱;
灝唍-1涓鐩樺瓙浠巄縐誨姩鍒癱;
}
榪欐牱灝卞畬鎴愪簡縐誨姩,濡傛灉鏄庣櫧浜嗚繖涓,閭ｄ箞鍓嶉潰鐨勫氨濂芥噦浜,
hanio(n-1,a,c,b); //鍥犱負hanio鍑芥暟瀹為檯縐誨姩鐨勬槸char a,char c,涔熷氨鏄絎浜屽拰絎鍥涗釜鍙傛暟,鎵浠ヨ繖鍎垮彲浠ョ湅鎴愭妸n-1涓鐩樺瓙浠巃縐誨姩鍒癰;
move(a,c);
hanio(n-1,b,a,c); //榪欏効鍙浠ョ湅鎴愭妸n-1涓鐩樺瓙浠巃縐誨姩鍒癰;

4. C語言漢諾塔問題，請問這個n=3的詳細步驟是什麼呀，大一新生沒聽懂

這是漢諾塔的演算法的問題。程序本身很簡單。

漢諾塔（又稱河內塔）問題是源於印度一個古老傳說的益智玩具。大梵天創造世界的時候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤。大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。並且規定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動一個圓盤。

這個主要是看演算法，再一個就是遞歸的學習，程序本身非常簡單。