C程序的汉诺塔问题. 用C语言编程序解决汉诺塔问题
\u6c49\u8bfa\u5854\u95ee\u9898\u7684C\u8bed\u8a00\u7a0b\u5e8f\u5e94\u8be5\u600e\u4e48\u5199\uff1f\u5e76\u8bf7\u8bf4\u660e\u4e00\u4e0b\u539f\u56e0\u5176\u5b9e\u4e3b\u8981\u5c31\u662f\u4e09\u4e2a\u6b65\u9aa4\uff1a\u7b2c\u4e00\uff0c\u628aa\u4e0a\u7684n-1\u4e2a\u76d8\u901a\u8fc7c\u79fb\u52a8\u5230b\u3002\u7b2c\u4e8c\uff0c\u628aa\u4e0a\u7684\u6700\u4e0b\u9762\u7684\u76d8\u79fb\u5230c\u3002\u7b2c\u4e09\uff0c\u56e0\u4e3an-1\u4e2a\u76d8\u5168\u5728b\u4e0a\u4e86\uff0c\u6240\u4ee5\u628ab\u5f53\u505aa\u91cd\u590d\u4ee5\u4e0a\u6b65\u9aa4\u5c31\u597d\u4e86\u3002#include void move(int n,char a,char b,char c){ if(n==1) printf("\t%c->%c\n",a,c); //\u5f53n\u53ea\u67091\u4e2a\u7684\u65f6\u5019\u76f4\u63a5\u4ecea\u79fb\u52a8\u5230c else { move(n-1,a,c,b); //\u7b2cn-1\u4e2a\u8981\u4ecea\u901a\u8fc7c\u79fb\u52a8\u5230b printf("\t%c->%c\n",a,c); move(n-1,b,a,c); //n-1\u4e2a\u79fb\u52a8\u8fc7\u6765\u4e4b\u540eb\u53d8\u5f00\u59cb\u76d8\uff0cb\u901a\u8fc7a\u79fb\u52a8\u5230c }} int main(){ int n; printf("\u8bf7\u8f93\u5165\u8981\u79fb\u52a8\u7684\u5757\u6570\uff1a"); scanf("%d",&n); move(n,'a','b','c'); return 0;}
#include "stdafx.h"
#include
#include
int count;
void movedisk(int,char,char,char);
int _tmain(int argc, _TCHAR* argv[])
{
int n;
printf("\u8f93\u5165\u76d8\u5b50\u7684\u6570\u91cf\uff1a");
scanf("%d",&n) ;
movedisk(n,'A','C','B');
printf("\u76d8\u5b50\u6570\u91cf%d\u7684\u65f6\u5019\u79fb\u52a8\u4e86%d\u6b21\n",n,count);
scanf("%d",&n) ;
}
void movedisk(int n,char from,char to,char tmp)
{
if(n>1)
movedisk(n-1,from,tmp,to);
printf("\u76d8\u5b50 %d \u53f7\u4ece\u67f1\u5b50 %c \u79fb\u52a8\u5230\u4e86\u67f1\u5b50 %c \u4e0a\n",n,from,to);
count++;
if(n>1)
movedisk(n-1,tmp,to,from);
}
n=3，x上有3个盘子，我们想经过y，把3个盘子都移到z上去，同时一直保持小盘在大盘上这一条件
执行步骤：
n=3，执行move函数里的else语句
move(2, x, z, y) //把2个盘子从x, 经过z, 移到y上去，此时x上还剩一最大盘
printf("%c-->%c\n",x,z); //打印语句表明，把x上最大盘直接移到z上
move(2,y,x,z); ////把2个盘子从y, 经过x, 移到z上去，这样z上就有了3个盘子，完毕
这里难以理解的一点应该是move(2, x, z, y)，因为我们无法直接看出到底是怎么把2个盘子从x移到y的。很多初学recursive function (递归函数)的朋友觉得这一点非常匪夷所思，并且思想上很难适应和接受。
剖析一下，move(2, x, z, y)是一个新的函数调用，它会继续往下执行，因为此时n=2，因此还是else条件：
move(1,x, y, z); //把1个盘子从x，经过y，移到z。注意此时move的第3、4个参数又调换了位置
这又是一个新的函数调用，此时n=1，执行if 语句
printf("%c-->%c\n",x,z); //直接把1个盘子从x移到z。很显然，此时z上的是最小的盘子
所以，递归函数的特点是不断调用新的函数，但每次其中的一个关键参数都会做递减运算（在这里是n），从而使得我们最终到达一个初始/最简条件，简单到我们一眼就能看出解法。我们先解决n=1的问题，再解决n=2的问题，逐步从底往上推移，最终解决n=n的问题。
由此可以看出，对于任何一个n，要得到一个解，我们首先要解决所有n=1,2...,n-1的子问题。这就是为什么递归函数写起来简单，但实际上有非常多的函数调用，在运算比较复杂的时候，耗时相比迭代法(iterative method, for/while loop)会更长的缘故。
递归函数的这一特质和一个重要的数据结构栈(stack)很像。事实上，递归函数的具体系统实现正是通过栈来做的。我们得到一个任务，需要解决n=3的问题，但我们并不马上去解决它，而是把它压栈(push to stack)，去解决n=2的问题。n=2又被压栈，接下来是n=1。n=1正是最简条件，我们就从它开始着手。解决了它之后，再出栈(pop stack)，一个个解决n=2, n=3...的问题。这不就是LIFO(Last in First out)么？基本上，可以用下图表示：
n=3的问题
n=2的问题
n=1的问题
调用函数从上到下，解决问题从下到上。解答完毕。
注：许多细节被省略，自己拿纸和笔写下来更直观。
是输入h=3吧
======================
这是一个递归过程，h=3时：
1.输出 the step to moving 03 diskes
2.调用move函数（n=3，x=a,y=b,z=c）
由于n!=1， 所以运行else内的语句：
i.move(n-1,x,z,y);，即n=2时调用move的过程
ii. 输出a-->c
iii.move(n-1,y,x,z);，即n=2时调用move的过程
这三步可把上面两个盘看作一个盘：即可把这三个盘看作2个盘的移动
（假设上面一个最小的盘和中间一个盘为一个整体，命名其为盘A，命名最下面的那个大盘为盘
B），这样就可以看做盘A和盘B在柱子上的移动：
i.把盘A移动到柱b（move(n-1,x,z,y);）
ii.把盘B移动到柱c（printf("%c-->%c\n",x,z);）
iii.把盘A移动到柱c（move(n-1,y,x,z);）
其中“把盘A移动到柱b”①与“把盘A移动到柱c”②
（即move(n-1,x,z,y)与move(n-1,y,x,z)）又是两个小过程：
设盘A中的两个盘上面的的一个为盘1，下面的那个为盘2
①：将盘1盘2组成的小塔从柱a移到塔柱b
②：将盘1盘2组成的小塔从柱b移到塔柱c（此时盘B已在柱c了）
======================全程序过=================================
move(3,a,b,c)
|-----move(2,a,c,b)
| |-----move(1,a,b,c)
| | |----printf("%c-->%c\n",a,c); a-->c
| | ----printf("%c-->%c\n",a,b); a-->b
| |-----move(1,c,a,b)
| | |----printf("%c-->%c\n",c,b); c-->b
|-----printf("%c-->%c\n",a,c); a-->c
|-----move(2,b,a,c)
| |-----move(1,b,c,a)
| | |----printf("%c-->%c\n",b,a); b-->a
| | ----printf("%c-->%c\n",b,c); b-->c
| |-----move(1,a,b,c)
| | |----printf("%c-->%c\n",c,a); a-->c
==============================================================
咱表达能力不好，有什么不明白的可以追问咱
move(int n,int x,int y,int z) //即将n个盘从柱x移到z
这里用递归实现，其实也不难理解（只要递归的思想模型具备了）：
递归其实也就跟数学归纳差不多，我们假设前n-1个盘用move函数实现了从x——>y，即move(n-1,x,z,y); 这时将第n个盘从x移到z，即printf("%c-->%c\n",x,z); 最后将y上的前n-1个盘移到z柱即可，即move(n-1,y,x,z); 每个递归都须有个入口点，这里是n==1的这种情况，只有一个盘时直接从x——>z便是。
那么具体n=3时，由x——>z是怎么实现的呢？
n=3时需要将前2个盘从x——>y,此后将第三个盘子由x——>z，最后将前2个盘从y——>z;
接下来看前2个盘怎么实现x——>y：
那就得将前1个盘从x——>z，这时再将第二个盘由x——>y，然后再将前一个盘从z——>y；
接下来又得看前一个盘如何实现x——>z了，这就是递归入口点，只要直接移动即可。
绛旓細閫掓帹鍏紡鐢辨璇炵敓锛歠(n) = 2 * f(n-1) + 1锛岃繖灏辨槸姹夎濉绉诲姩娆℃暟鐨勯掑綊琛ㄨ揪銆備笉濡ㄧ湅鐪嬩唬鐮佺ず渚嬶紝閫氳繃C璇█锛屾垜浠彲浠ョ紪鍐欒繖鏍风殑鍑芥暟鏉ヨ绠楋細<stdio.h>int hanoi_step(int n) { if (n <= 1) return 1; else return 2 * hanoi_step(n - 1) + 1;}main() { int n, ...
绛旓細hannuo(n-2, b, c, a, d);int main(){ char a='a', b='b', c='c', d = 'd';int i;cout<<"璇疯緭鍏ョ洏瀛愮殑涓暟";while (cin>>i){ hannuo(i, a, b, c, d);return 0;
绛旓細闈㈣瘯鍑嗗鏃讹紝閲嶆俯缁忓吀绠楁硶锛姹夎濉妗堜緥涔嬩竴銆闂鑳屾櫙锛氭湁涓夋牴閽圓銆丅銆C锛孉閽堜笂鏀剧疆N涓洏瀛愶紝鎸夊ぇ灏忛『搴忎粠涓嬪埌涓婃帓鍒椼備换鍔℃槸灏嗘墍鏈夌洏瀛愪粠A閽堝叏閮ㄧЩ鍔ㄥ埌C閽堬紝瑙勫垯鏄瘡娆″彧鑳界Щ鍔ㄤ竴涓洏瀛愶紝涓旂Щ鍔ㄨ繃绋嬩腑鎵鏈夐拡涓婄洏瀛愬潎淇濇寔澶у湪涓嬪皬鍦ㄤ笂銆傛牳蹇冩蹇碉細鍔ㄦ佸唴瀛樺垎閰嶄笌鏁扮粍鐢熷瓨鍛ㄦ湡 鏁扮粍鍏冪礌鍦ㄥ唴瀛樹腑鎸夌収椤哄簭...
绛旓細n=1姝ｆ槸鏈绠鏉′欢锛屾垜浠氨浠庡畠寮濮嬬潃鎵嬨傝В鍐充簡瀹冧箣鍚庯紝鍐嶅嚭鏍(pop stack)锛屼竴涓釜瑙ｅ喅n=2, n=3...鐨勯棶棰樸傝繖涓嶅氨鏄疞IFO(Last in First out)涔堬紵鍩烘湰涓婏紝鍙互鐢ㄤ笅鍥捐〃绀猴細n=3鐨勯棶棰 n=2鐨勯棶棰 n=1鐨勯棶棰 璋冪敤鍑芥暟浠庝笂鍒颁笅锛岃В鍐抽棶棰樹粠涓嬪埌涓娿傝В绛斿畬姣曘傛敞锛氳澶氱粏鑺傝鐪佺暐锛岃嚜宸辨嬁绾稿拰...
绛旓細杩欐牱锛岀劧鑰岋紝瀹屾垚绗竴姝ュ拰绗笁姝ヤ篃鍚屾牱鏄竴涓Щ鍔╪-1涓洏瀛鐨勬眽璇哄闂銆備簬鏄紝閫掑綊璋冪敤鍦ㄨ繖閲屼笉鍙伩鍏嶃绋嬪簭浣犲凡缁忓啓鐨勫緢娓呮锛岀粰浣犺В閲婁竴涓嬨傜幇鎶婁綘鐨勭▼搴忕敾涓婅浠ヤ究璇存槑銆1 #include "stdio.h"2 main()3 {void hanoi(int,char,char,char); 4 int m; 5 printf("input the number of di...
绛旓細閫掑綊绠楁硶鐨勫嚭鍙戠偣涓嶆槸鐢卞垵濮嬫潯浠跺嚭鍙戯紝鑰屾槸鎶婂嚭鍙戠偣鏀惧湪姹傝В鐨勭洰鏍囦笂锛屼粠鎵姹傜殑鏈煡椤瑰嚭鍙戦愭璋冪敤鏈韩鐨勬眰瑙ｈ繃绋嬶紝鐩村埌閫掑綊鐨勮竟鐣岋紙鍗冲垵濮嬫潯浠讹級銆姹夎濉旈棶棰鐨勯噸鐐规槸鍒嗘瀽绉诲姩鐨勮鍒欙紝鎵惧埌瑙勫緥鍜岃竟鐣屾潯浠躲傝嫢闇瑕佸皢n涓洏瀛愪粠A绉诲姩鍒C灏遍渶瑕侊紙1锛夊皢n-1涓洏瀛愪粠A绉诲姩鍒癇锛涳紙2锛夊皢浣犵n涓粠A绉诲姩鍒癈锛...
绛旓細杩欎釜闂浣犺鍏堟妸閫掑綊鎼炴噦鎵嶈兘鐞嗚В鐨, 鏈濂芥槸鍗曡窡韪墽琛屼竴涓, 鎴戣繖閲屽氨绠鍗曡涓涓嬪惂!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绉诲埌bmove( 'a', 'c'); //鎶...
绛旓細(3)鍙嶅杩涜(1)(2)鎿嶄綔,鏈鍚庡氨鑳芥寜瑙勫畾瀹屾垚姹夎濉旂殑绉诲姩銆 鎵浠ョ粨鏋滈潪甯哥畝鍗,灏辨槸鎸夌収绉诲姩瑙勫垯鍚戜竴涓柟鍚戠Щ鍔ㄩ噾鐗: 濡3闃舵眽璇哄鐨勭Щ鍔:A鈫C,A鈫払,C鈫払,A鈫扖,B鈫扐,B鈫扖,A鈫扖 姹夎濉旈棶棰涔熸槸绋嬪簭璁捐涓殑缁忓吀閫掑綊闂,涓嬮潰鎴戜滑灏嗙粰鍑洪掑綊鍜岄潪閫掑綊鐨勪笉鍚屽疄鐜版簮浠ｇ爜銆 鏈洖绛旂敱鎻愰棶鑰呮帹鑽 涓炬姤| 绛旀绾犻敊...
绛旓細銆愪緥銆Hanoi濉旈棶棰 涓鍧楁澘涓婃湁涓夋牴閽堬紝A锛孊锛C銆侫閽堜笂濂楁湁64涓ぇ灏忎笉绛夌殑鍦嗙洏锛屽ぇ鐨勫湪涓嬶紝灏忕殑鍦ㄤ笂銆傚鍥5.4鎵绀恒傝鎶婅繖64涓渾鐩樹粠A閽堢Щ鍔–閽堜笂锛屾瘡娆″彧鑳界Щ鍔ㄤ竴涓渾鐩橈紝绉诲姩鍙互鍊熷姪B閽堣繘琛屻備絾鍦ㄤ换浣曟椂鍊欙紝浠讳綍閽堜笂鐨勫渾鐩橀兘蹇呴』淇濇寔澶х洏鍦ㄤ笅锛屽皬鐩樺湪涓娿傛眰绉诲姩鐨勬楠ゃ傛湰棰樼畻娉曞垎鏋愬涓嬶紝...
绛旓細鍏堢湅hanoi(1, one, two, three)鐨勬儏鍐点傝繖鏃剁洿鎺ュ皢one鏌变笂鐨勪竴涓洏瀛愭惉鍒皌hree鏌变笂銆傛敞鎰忥紝杩欓噷one鏌辨垨three鏌卞埌搴曟槸A銆丅杩樻槸C骞朵笉閲嶈锛岃璁颁綇鐨勬槸鍑芥暟绗簩涓弬鏁颁唬琛ㄧ殑鏌变笂鐨勪竴涓洏琚惉鍒扮鍥涗釜鍙傛暟浠ｈ〃鐨勬煴涓娿備负鏂逛究锛屽皢杩欎釜鍔ㄤ綔璁颁负锛歰ne =銆媡hree鍐嶇湅hanoi(2, one, two, three)鐨勬儏鍐...
