C语言汉诺塔 C语言--汉诺塔程序执行步骤
C\u8bed\u8a00\u6c49\u8bfa\u5854\u7a0b\u5e8f\u5c06\u4ee5\u4e0b\u5185\u5bb9\u5168\u90e8\u590d\u5236\u5230\u65b0\u5efa\u7684\u6e90\u6587\u4ef6\u4e2d\uff1a\uff08\u672c\u4eba\u81ea\u5df1\u5199\u7684\uff0c\u56e0\u4e3a\u4f60\u90a3\u8bfe\u672c\u4e0a\u7684\u4ee3\u7801\uff0c\u6ca1\u89e3\u91ca\uff0c\u4e66\u5199\u4e0d\u89c4\u8303\uff0c\u5f88\u96be\u7406\u89e3\u6e05\u695a\uff0c\u6240\u4ee5\u6211\u76f4\u63a5\u65b0\u5199\u4e86\u4e00\u4e2a\u5b8c\u6574\u7684\u4ee3\u7801\uff0c\u9644\u5e26\u8be6\u7ec6\u8bf4\u660e\uff09
#include
//\u6c49\u8bfa\u5854x\u5c42\u5854\u4eceA\u5854\u6574\u4f53\u642c\u5230C\u5854\uff0c\u4e2d\u95f4\u4e34\u65f6B\u5854\u3002
//x\u5c42\u5854\u662f\u4ece\u5927\u5230\u5c0f\u5f80\u4e0a\u53e0\u653e\u3002\u6bcf\u6b21\u79fb\u52a8\u53ea\u80fd\u79fb\u52a8\u4e00\u5c42\u5854\u3002\u5e76\u4e14\u5728\u79fb\u52a8\u8fc7\u7a0b\u4e2d\u5fc5\u987b\u4fdd\u8bc1\u5c0f\u5c42\u5728\u4e0a\u8fb9
//\u501f\u52a9B\u5854\u53ef\u4ee5\u5c06x\u5c42\u5854\u5168\u90e8\u4eceA\u642c\u5230C\u4e0a\uff0c\u5e76\u4e14\u7b26\u5408\u8981\u6c42\uff08\u5728\u79fb\u52a8\u8fc7\u7a0b\u4e2d\u5927\u7684\u90a3\u5757\u5728\u4e0b\u8fb9\uff0c\u5c0f\u7684\u90a3\u5757\u5728\u4e0a\u8fb9\uff09
int main()
{
void tower(int x,char a,char b,char c);//\u58f0\u660e\u51fd\u6570
int x=5,a='A',b='B',c='C';//x\u8868\u793a\u67095\u5c42\u5854\uff0c\u5177\u4f53\u8981\u591a\u5c11\u5c42\u81ea\u5df1\u4fee\u6539\u8fd9\u4e2a\u503c\u3002abc\u5206\u522b\u8868\u793aABC\u5854\u3002
tower(x,a,b,c);//x\u5c42\u5854\u4ecea\u79fb\u52a8\u5230c\u7684\u5168\u8fc7\u7a0b\uff0c\u4e3b\u7a0b\u5e8f\u53ea\u6709\u8fd9\u6761\u6709\u6548\u8bed\u53e5
return 0;
}
//\u4ee5\u4e0b\u662ftower\u51fd\u6570\u7684\u5b9a\u4e49
//\u53c2\u6570\u89e3\u6790\uff1ax\u5c42\u5854\u653e\u5728a\u4e0a\uff0cb\u662f\u4e2d\u95f4\u5854\uff0cc\u662f\u76ee\u6807\u5854\u3002\u5373x\u5c42\u5854\u8981\u4ecea\u642c\u5230c\u4e0a\u3002
//\u6b64\u51fd\u6570\u5b9e\u73b0x\u5c42\u5854\u4ecea\u6574\u4f53\u8f6c\u79fb\u5230c\u4e0a\u3002\u4ee5\u53ca\u8fd9\u4e2a\u8fc7\u7a0b\u662f\u600e\u4e48\u642c\u7684\u5168\u90e8\u8fc7\u7a0b\u3002
void tower(int x,char a,char b,char c)
{
if(x==1)printf("\u5c06%d\u4ece%c\u653e\u5230%c\n",x,a,c);//\u53ea\u67091\u5c42\u5854\u65f6\uff0c\u76f4\u63a5\u4ecea\u642c\u5230c\u4e0a\u3002
else //\u4e0d\u6b621\u5c42\u5854\uff0c\u5219\u5148\u5c06x-1\u5c42\u5854\u4ecea\u6309\u7167\u89c4\u5f8b\u642c\u5230b\u4e0a\uff0c\u518d\u5c06\u6700\u540e\u4e00\u5757\u4ecea\u642c\u5230c\u4e0a\uff0c\u6700\u540e\u518d\u5c06b\u4e0a\u7684x-1\u5c42\u5854\u6309\u7167\u89c4\u5f8b\u642c\u5230c\u4e0a\u3002
{
tower(x-1,a,c,b);//\u5148\u5c06x-1\u5c42\u5854\u4ecea\u6309\u7167\u89c4\u5f8b\u642c\u5230b\u4e0a\uff0c\u6ce8\u610f\u53c2\u6570b\u653e\u5728\u6700\u540e\uff0c\u56e0\u4e3a\u653e\u5728\u6700\u540e\u7684\u53c2\u6570\u662f\u51c6\u5907\u642c\u8fc7\u53bb\u7684\u76ee\u6807\u5854\u3002
printf("\u5c06%d\u4ece%c\u653e\u5230%c\n",x,a,c);//\u5c06\u6700\u540e\u4e00\u5757\u4ecea\u642c\u5230c\u4e0a
tower(x-1,b,a,c);//\u6700\u540e\u518d\u5c06b\u4e0a\u7684x-1\u5c42\u5854\u6309\u7167\u89c4\u5f8b\u642c\u5230c\u4e0a\uff0c\u6ce8\u610f\u53c2\u6570b\u653e\u5728\u5f00\u5934\uff0c\u56e0\u4e3ax-1\u5c42\u662f\u8981\u4eceb\u4e0a\u642c\u8fc7\u53bb\u7684\u3002
}
}
\u8fd9\u4e2a\u95ee\u9898\u4f60\u8981\u5148\u628a\u9012\u5f52\u641e\u61c2\u624d\u80fd\u7406\u89e3\u7684, \u6700\u597d\u662f\u5355\u8ddf\u8e2a\u6267\u884c\u4e00\u4e0b, \u6211\u8fd9\u91cc\u5c31\u7b80\u5355\u8bf4\u4e00\u4e0b\u5427!
hanoi(5, 'a', 'b', 'c');\u628a5\u4e2a\u4ece'a'\u79fb\u5230'c'
\u8fd9\u65f6n=5, noe='a', two='b', three='c'
\u56e0\u4e3an!=1, \u6267\u884celse\u91cc\u7684
hanoi( 4, 'a', 'c', 'b'); //\u628a\u4e0a\u97624\u4e2a\u4ecea\u79fb\u5230b
move( 'a', 'c'); //\u628a\u7b2c5\u4e2a\u4ecea\u79fb\u5230c
hanoi( 4, 'b', 'a', 'c'); //\u518d\u628a\u90a34\u4e2a\u4eceb\u79fb\u5230c
\u4e0a\u9762\u7684\u5f88\u597d\u660e\u767d\u7684, \u518d\u5206\u6790hanoi( 4, 'a', 'c', 'b'); //\u628a\u4e0a\u97624\u4e2a\u4ecea\u79fb\u5230b,\u4e5f\u662f\u6267\u884celse
hanoi( 3, 'a', 'b', 'c'); //\u628a\u4e0a\u97623\u4e2a\u4ecea\u79fb\u5230c
move( 'a', 'b'); //\u628a\u7b2c4\u4e2a\u4ecea\u79fb\u5230b
hanoi( 4, 'c', 'a', 'b'); //\u518d\u628a\u90a33\u4e2a\u4ecec\u79fb\u5230b
\u4e00\u76f4\u5230n=1\u624d\u7ed3\u675f
要看懂递归程序，往往应先从最简单情况看起。
先看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柱上。这就是我们所需要的结果！
根据汉诺塔的游戏规则可知，若只有一个盘子，则只要直接搬运就可以了，其它的不需要再做。return语句的作用，就是遇到它时，程序直接返回到调用它的地方，不再执行此函数中return语句以后的代码。
不过这里这个return语句也可以不写，只是代码要稍作更改（代码的执行还是不变的，即与更改前完全等价）：
void hanNuoTa(int n, char from, char to, char helper)
{
if(n==1)
{
printf("%c --->%c
",from,to);
}
else
{
hanNuoTa(n-1, from, helper, to);
printf("%c ---> %c
",from,to);
hanNuoTa(n-1, helper, to, from);
}
}
绛旓細include\x0d\x0a void move(char x,char y)\x0d\x0a {\x0d\x0a printf("%c-->%c\n",x,y);\x0d\x0a }\x0d\x0a void hanoi(int n,char one ,char two,char three)\x0d\x0a {\x0d\x0a if(n==1) move(one,three);\x0d\x0a else\x0d\x0...
绛旓細鍙互浣跨敤C璇█鏍囧噯搴撲腑鐨則ime.h澶存枃浠朵腑鐨刢lock()鍑芥暟鏉ヨ幏鍙栫▼搴忚繍琛屾椂闂淬傚叿浣撶殑鏂规硶濡備笅锛氬湪绋嬪簭寮濮嬭繍琛屾椂锛岃皟鐢╟lock()鍑芥暟锛岃幏鍙栧綋鍓嶇郴缁熸椂闂达紝骞跺皢缁撴灉淇濆瓨鍦ㄤ竴涓彉閲忎腑锛屽start_time銆傜▼搴忔墽琛屽畬姣曞悗锛屽啀娆¤皟鐢╟lock()鍑芥暟锛岃幏鍙栧綋鍓嶇郴缁熸椂闂达紝骞跺皢缁撴灉淇濆瓨鍦ㄥ彟涓涓彉閲忎腑锛屽end_time銆傝绠楃▼搴...
绛旓細c璇█璇佹槑姹夎濉娆℃暟鍏紡锛歠(k+1锛=2*f(k)+1鏉ヨ绠椼俰nclude<stdio.h> usingnamespacestd defineMOD1000000 longlongcal锛坙onglonga锛宨ntn锛宨ntm锛塴onglongans=1 a=a%m while锛坣锛塧ns=锛坅ns*a锛%m n=n>>1 a=锛坅*a锛%m锛// returnans锛沬ntmain锛坴oid锛塱ntn锛宨锛宮锛宎ns scanf锛"%d"...
绛旓細void movedisc(unsigned n,char fromneedle,char toneedle,char usingneedle);int i=0;int 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'); /*浠嶢涓婂熷姪B灏哊涓...
绛旓細绋嬪簭浠ｇ爜 include <stdio.h> int main(){ int hanoi(int,char,char,char);int n,counter;printf("Input the number of diskes锛");scanf("%d",&n);printf("\n");counter=hanoi(n,'A','B','C');return 0;} int hanoi(int n,char x,char y,char z){ int move(char,int,char)...
绛旓細int pan[3];void dizuo(){ setlinestyle(PS_SOLID,NULL,4); line(20,400,160,400); line(90,200,90,400); line(220,400,360,400); line(290,200,290,400); line(420,400,560,400); line(490,200,490,400);}//鍒濆鍖姹夎濉void hanoi_draw(...
绛旓細姹夎濉锛圚anoi锛夋槸蹇呴』鐢ㄩ掑綊鏂规硶鎵嶈兘瑙ｅ喅鐨勭粡鍏搁棶棰樸傚畠鏉ヨ嚜浜庡嵃搴︾璇濄備笂甯濆垱閫犱笘鐣屾椂浣滀簡涓夋牴閲戝垰鐭虫煴瀛愶紝鍦ㄧ涓鏍规煴瀛愪笂浠庝笅寰涓婃寜澶у皬椤哄簭鎽炵潃64鐗囬粍閲戝渾鐩橈紝濡傚浘7-3鎵绀恒備笂甯濆懡浠ゅ﹩缃楅棬鎶婂渾鐩樹粠涓嬮潰寮濮嬫寜澶у皬椤哄簭閲嶆柊鎽嗘斁鍒扮浜屾牴鏌卞瓙涓婏紝骞朵笖瑙勫畾锛屾瘡娆″彧鑳界Щ鍔ㄤ竴涓渾鐩橈紝鍦ㄥ皬鍦嗙洏涓婁笉鑳芥斁澶у渾鐩...
绛旓細hanoi('a','b','c',n,num);} void move(char x,char y,struct H num[3])/*绉诲姩鐨勫叿浣撹繃绋*/ { int i;char num1[3],num2[3];sprintf(num1,"%c",x-32);/*灏嗗皬鍐欏彉鎴愬ぇ鍐欙紝骞惰浆鎹㈡垚瀛楃涓茶緭鍑*/ sprintf(num2,"%c",y-32);setfillstyle(SOLID_FILL,BLACK);/*鎶婂師鏉ョ殑鍦版柟...
绛旓細閫掑綊绠楁硶鐨勫嚭鍙戠偣涓嶆槸鐢卞垵濮嬫潯浠跺嚭鍙戯紝鑰屾槸鎶婂嚭鍙戠偣鏀惧湪姹傝В鐨勭洰鏍囦笂锛屼粠鎵姹傜殑鏈煡椤瑰嚭鍙戦愭璋冪敤鏈韩鐨勬眰瑙ｈ繃绋嬶紝鐩村埌閫掑綊鐨勮竟鐣岋紙鍗冲垵濮嬫潯浠讹級銆姹夎濉闂鐨勯噸鐐规槸鍒嗘瀽绉诲姩鐨勮鍒欙紝鎵惧埌瑙勫緥鍜岃竟鐣屾潯浠躲傝嫢闇瑕佸皢n涓洏瀛愪粠A绉诲姩鍒C灏遍渶瑕侊紙1锛夊皢n-1涓洏瀛愪粠A绉诲姩鍒癇锛涳紙2锛夊皢浣犵n涓粠A绉诲姩鍒癈锛...
绛旓細鍏跺疄涓昏灏辨槸涓変釜姝ラ锛氱涓锛屾妸a涓婄殑n-1涓洏閫氳繃c绉诲姩鍒癰銆傜浜岋紝鎶奱涓婄殑鏈涓嬮潰鐨勭洏绉诲埌c銆傜涓夛紝鍥犱负n-1涓洏鍏ㄥ湪b涓婁簡锛屾墍浠ユ妸b褰撳仛a閲嶅浠ヤ笂姝ラ灏卞ソ浜嗐#include<stdio.h> void move(int n,char a,char b,char c){ if(n==1) printf("\t%c->%c\n",a,c); //...
