资源描述:
《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