C语言实现汉诺塔的执行过程

源来缘爱 发布于 2013/08/11 15:54
阅读 2K+
收藏 0
1       #include "stdio.h" 
2       main() 
3       {void hanoi(int,char,char,char); 
4       int m; 
5       printf("input the number of disks:"); 
6       scanf("%d",&m); 
7       printf("The step to moving %d disks:\n",m); 
8       hanoi(m,'A','B','C'); 
9       } 
10      void hanoi(int n,char a,char b,char c) 
11      {//void move(char,char); 
12      if(n==1) move(a,c); 
13      else 
14      {hanoi(n-1,a,c,b); 
15      move(a,c); 
16      hanoi(n-1,b,a,c); 
17      } 
18      } 
19      void move(char x,char y) 
20      {printf("%c-->%c\n",x,y); 
21      } 

当m=4时,程序走到第8行,调用函数hanoi(int n,char a,char b,char c)。此时,实参把值传递给了形参,于是此时,n=4,a=A,b=B,c=C。我把第11行的void move(char,char); 注释掉了,应该知道这一句的意思。因为这一行虽然可以让程序更加完整,但是解释的时候加上它会很麻烦。程序走到第12行,因为此时n=4,而不等于1,程序直接走第13行。于是调用第14行的hanoi(n-1,a,c,b)。这是一个递归调用。此时,n=3,a=A,c=B,b=C。要清楚,A,B,C代表的意义。A代表初始柱子,B代表辅助柱子,C代表目标柱子。而a代表第一根柱子,b代表第二根柱子,c代表第三根柱子。这是不一样的。程序继续走,到12行时n依然不等于1。走到14行调用hanoi(n-1,a,c,b)。此时,n=2,a=A,c=C,b=B。程序再走,到12行时n依然不等于1,走到14行调用hanoi(n-1,a,c,b)。此时,n=1,a=A,c=B,b=C。程序走到12行时发现n=1,程序开始走15行。调用move(char x,char y)到20行时输出A-->B。调用结束,回到上一个调用即n=2,a=A,c=C,b=B。程序回到第15行,输出 A-->B。再走第16行,调用hanoi(n-1,b,a,c)。此时n=1,b=A,a=B,c=C。程序回到12行再调用19行输出B-->C。调用结束,回到上一个调用n=3,a=A,c=B,b=C。程序走到15行,输出A-->C,这时,第一根柱子上有一个盘子,第二根柱子上有一个盘子,第三根柱子上有两个盘子。再调用16行就可以完成把第三根柱子里的所有盘子都移动到第二根柱子上。这样。我们就完成了整体目标的第一步。把n个盘子除了最下面的盘子以外的所有盘子从第一根柱子(初始柱子)移动到中间那个柱子上(辅助柱子),调用完成后程序回到15行,此时n=3,a=A,c=B,b=C。15行时输出A-->C,这时便完成了整体目标的第二步,最下面的盘子移动到最后一根柱子上(目标柱子)。再根据程序走到16行,经过跟14行类似的一系列的递归调用,我们就可以完成最终目标了。


上面网友解释的已经很详细了,可是我不明白每次在调用Hanoi函数的时候,a,b,c是怎么赋值的,像n=3,a=A,c=B,b=C,n=2,a=A,c=C,b=B,n=1,a=A,c=B,b=C这是怎么来的,变化的依据是什么?
请大家指点指点吧,疑惑我好几天了。
加载中
1
中山野鬼
中山野鬼

引用来自“源来缘爱”的答案

引用来自“中山野鬼”的答案

你先把堆栈了解清楚,然后讨论下反递归的写法,那么你就清楚了。递归是在是无聊的东西。
赶脚好有学术争论的feel,不过我还得仔细琢磨。

反递归需要用到堆栈,其实汉诺塔是个说明堆栈的非常好的例子,结果被应用反了,用来解释递归,自然你递归不了解了。了解递归你可以看下面的例子,我们计算 1+2+3.。。+1000等于几,不使用循环方式,你可以理解为它在 做这样的事情。

t = t + i;

i = i+1;

那么

int add_next(int i){
 int re = 0;
 if (i < 1000){
     re = add_next(i+1);          
   }
     re += i;
   return re;

}
每次递归进入一个函数,做两件事,先去调用自身,但是传递的参数为比自己大1的数,并且计算它们的结果。调用完成后,将自己再加上去。如果用公式描述则如下:

t = (0 + (1+ (2+(3+(4+ ...(999 + (1000)))))))));

你再抽象则为

t = (i0 + ((i1 = i0 + 1) + ((i2 = i1+1) + ((i3 = i2+1) + .... (i999 + (i1000 = i999 +1))))))))

不知道现在是否理解递归了。。。

0
中山野鬼
中山野鬼
你先把堆栈了解清楚,然后讨论下反递归的写法,那么你就清楚了。递归是在是无聊的东西。
中山野鬼
中山野鬼
回复 @Yu_Yang : 递归首先对上下文的数据保存并不能甄别和优化,其次,对递归深度如果没有限制,会导致程序存在潜在bug。而反递归设计就是用于解决这两个问题。其他高级语言所谓的支持,说实话是“不实用”的偷懒主义,不实用指,不可实用。
Yu_Yang
Yu_Yang
回复 @中山野鬼 : 递归不只是哲学或者数学上的概念,编程也有应用,支持尾递归优化的语言,递归应用广泛, for while之类的循环不都是些语法糖吗?当然因为C的特殊性,确实不适合递归
中山野鬼
中山野鬼
回复 @Yu_Yang : 我的讨论范围是编程,所以有了反递归这个名词,递归本身是数学或哲学上逻辑概念,这个我不反对,反递归数学和哲学上是没有这个说法的。但在编程时,非常不可取。这也是实话。哈。
Yu_Yang
Yu_Yang
野鬼童鞋,虽然我很尊重你,但我不得不吐槽一下,递归绝对不是无聊的东西,都怪天朝那些天杀的老师把递归说的一无是处,实际上,递归是超级重要的思想好不好?好多问题,你不从递归的角度思考,那压根无解
0
雨翔河
雨翔河
不怕麻烦的话你拿笔写出每一步就明白了。 另:麻烦以后贴代码规范一点,不要直接这个弄过来,OSC有写代码的地方。
源来缘爱
源来缘爱
好的,谢谢!
0
张云昊
张云昊
你动手试一下就理解了,在这里函数调用传的是值,值一直在变。我也是新手规范不规范就不说了,至少缩进别省了啊。
源来缘爱
源来缘爱
谢谢,我会多注意规范化的。
0
中山野鬼
中山野鬼
@Yu_Yang  补充说下,递归不可取的理由是,我们的运行环境都是有限的。包括浮点计算也是应该尽量回避的。毕竟大家都知道,浮点描述法并不能保障精度。因为步长是变动的。但现实计算种确实有很多非整型计算。不过落到计算机上,要保障精度,还是做大位宽的整型处理比浮点要好。否则中间加加减减,乘乘除除的,一不小心误差扩散,结论就会走样。这也是个数学上的东西,落到计算机,不好折腾的例子。哈。
0
源来缘爱
源来缘爱

引用来自“中山野鬼”的答案

你先把堆栈了解清楚,然后讨论下反递归的写法,那么你就清楚了。递归是在是无聊的东西。
赶脚好有学术争论的feel,不过我还得仔细琢磨。
返回顶部
顶部