汉诺塔问题C语言程序设计.doc

三峡大学理学院2011级电信专业 《高级语言程序设计》课程设计 说明书 ? 设计题目: 汉诺塔的搬移过程设计 ? 班 级：高级语言程序设计1 班 ? 学 号：2011142227 ? 姓 名：徐飞 ? 完成日期：2012 年6月20日 1设计任务 设计题目：用递归法计算解决汉诺塔问题，并能够演示解决汉诺塔问题过； 要求：设计一个运用递归法计算解决汉诺塔问题C语言程序； 2 汉诺（Hanoi）塔问题的提出 古代有一个梵塔，塔内有A,B,C，3个座，座A上有64个大小不等的盘子，大的在下，小的在上（如下图）。有一个和尚想把这64个盘子从座A全部移到座C ，在移动过程中可以借用座A，座B或座C,但每次只允许移动一个盘子，并且不允许大盘放在小盘的上面。 3编程思路 首先，要找出递归的两个关键点，即： 递归终止条件：只有一个盘子时，可以移动。 递归表达式：要找出递归表达式，可以如下设想： 下面以3个盘子为例说明详细的移动过程： (1)将座A上的2个盘子移动到座B上； (2)将座A上的1个盘子移动到座C上； (3)将座B上的2个盘子移动到座C上； 上面第1步可用递归方法分解为： （1）将座A上的1个盘子从座A移动到座C上； （2）将座A上的1个盘子从座A移动到座B上； (3)将座C上的1个盘子从座C移动到座B上； 第（3）步可用递归方法分解为： （1）将座B上的1个盘子从座B移动到座A上； （2）将座B上的1个盘子从座B移动到座C上； （3）将座B上的1个盘子从座A移动到座C上; 第（1）步操作可归纳为：将座A上的2个盘子借助座C移到座B; 第（3）步操作可归纳为：将座B上的2个盘子借助座A移到座C; 因此，将n个盘子从座A移到座C可以描述为： 将n-1个盘子从座A借助座C移到座B; 将剩下的一个盘子从座A移到座C; 将n-1个盘子从座B借助座A移到座C; 3系统操作流程图; 4.程序说明； 函数HN(int n,char a,char b,char c)表示将n个盘子从座A移到座C,移动过程中借助B 关键语句：HN(n-1,a,c,b)； printf(from %c to %c\n,a,c)； HN(n-1,b,a,c); 假设盘子数为2、5，则其运行过程为： 5源程序附录； #includestdio.h void main() { void HN(int n,char a,char b,char c); int m; printf(请输入盘子的个数:); scanf(%d,m); printf(%d个盘子移动的步骤如下:\n,m); HN(m,A,B,C); } void HN(int n,char a,char b,char c) { if(n==1) printf(from %c to %c\n,a,c); else { HN(n-1,a,c,b); printf(from %c to %c\n,a,c); HN(n-1,b,a,c); } } 第一步：将64个盘子的问题简化为63个盘子的问题，分三步完成移动操作： （1）先将上面的63个盘子看成一个整体，从座A移到座B; （2）再将剩下的一个盘子（第64个，也是最大的一个）从座A移动到座C； （3）最后将63个盘子从座B移到座C。 第二步，将63个盘子的问题简化成62个盘子的问题，同样分3步完成操作。 再将62个盘子的问题简化成61个盘子问题。依此规律，每次重复上面的三步，这样层层递归，直到最后只有一个盘子为止。 开始 Scanf(%d,m); “请输入盘子的个数：” 显示盘子的移动步骤； 结束 调用HN函数 HN函数开始 If(n==1) Printf(“盘子的移动步骤”) else If(n==n-1) 继续运行 HN递归调用