资源描述：
《C语言程序设计教学全套-11汉诺塔问题.pptx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、汉诺塔问题主讲人：刘斌02问题1:古代有一个梵塔，塔内有三个柱A、B、C，A柱上有64个盘子，盘子大小不等，大的在下，小的在上（如图5-15）。有一个和尚想把这64个盘子从A柱移到C柱，但每次只能允许移动一个盘子，并且在移动过程中，3个柱上的盘子始终保持大盘在下，小盘在上。在移动过程中可以借助B柱，要求打印移动的步骤。初始时，只有A柱上有盘，目的就是通过B柱移动到C柱上。递归函数的应用对于n个盘子的汉诺塔，设从上到下n个盘子的编号分别为1，2，…，n，三根柱分别叫做起始柱，目标柱和辅助柱。当n等于1时可以直接由起始柱移动到目标柱。当n>1
2、时显然不能直接移动，此时可以把起始柱上最上面的n-1个盘子看作是一个逻辑盘，最下面的一个盘子看作是物理盘。首先对该问题进行分析，分析结论如下：ABC递归函数的应用只需要下面三步就可以完成任务了。03把逻辑盘从起始柱移动到辅助柱。把物理盘从起始柱移动到目标柱。把逻辑盘从辅助柱移动到目标柱。ABC递归关系可表示为：1．把A柱上的前n-1个盘子借助C柱移到B柱，即Hanoi(n-1,A,C,B)。2．把第n号盘子从A柱移到C柱，即Print(n,A,C)。3．把B柱上的n-1个盘子借助A柱移到C柱，即Hanoi(n-1,B,A,C)。递归函数的
3、应用04递归函数的应用05（1）#include"stdio.h"（2）voidHanoi(intn,charA,charB,charC)（3）{（4）if(n==1)（5）{（6）printf("将%d号盘子从%c柱移动到%c柱",n,A,B);（7）}（8）else（9）{（10）Hanoi(n-1,A,C,B);（11）printf("将%d号盘子从%c柱移动到%c柱",n,A,B);（12）Hanoi(n-1,C,B,A);（13）}（14）}（15）intmain()（16）{（17）intn;（18）printf("请
4、输入汉诺塔盘子个数：");（19）scanf("%d",&n);（20）Hanoi(n,'A','B','C');printf("%d",sum);（21）return0;（22）}递归函数的应用调用和回代过程06下面以n=3为例说明调用回代过程，如PPT所示。图中可以看到用H(n-1,A,B,C)代替Hanoi(n-1,A,B,C)，用P(n,A,B)代替Print(n,A,B)，⑼⑴⑵⑶⑷⑸⑹⑺⑻⑽⑾⑿H(3,A,B,C){H(2,A,C,B);P(3,A,B);H(2,C,B,A);}H(2,A,C,B){H(1,A,B,C
5、);P(2,A,C);H(1,B,C,A);}H(2,C,B,A){H(1,C,A,B);P(2,C,B);H(1,A,B,C);}H(1,A,B,C){P(1,A,B);}H(1,B,C,A){P(1,B,C);}H(1,C,A,B){P(1,C,A);}H(1,A,B,C){P(1,A,B);}课堂实践对给定的函数voidP(intw)，画出当w=3时p(3)的调用和回代图，并给出P(3)的输出结果。voidP(intw){if(w>0){P(w-1);printf("%4d",w);P(w-1);}}再见07
