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

汉诺塔问题C语言程序设计
三峡大学理学院2011级电信专业
《高级语言程序设计》课程设计
说明书
设计题目：汉诺塔的搬移过程设计
班级：高级语言程序设计 1班
学 号：2011142227
姓名：徐飞
完成日期：2012年6月20日
1设计任务
设计题目：用递归法计算解决汉诺塔问题，并能 够演示解决汉诺塔问题过；
要求：设计一个运用递归法计算解决汉诺塔问 题C语言程序；
2汉诺（Hanoi）塔问题的提出
古代有一个梵塔，塔内有 A,B,C, 3个座，座 A上有64个大小不等的盘子，大的在下，小的 在上（如下图）。有一个和尚想把这 64个盘子
从座A全部移到座C，在移动过程中可以借用 座A,座B或座C,但每次只允许移动一个盘子， 并且不允许大盘放在小盘的上面。
吕座 B療 C座
即：
可以移动。
可以如下设想:
3编程思路
首先，要找出递归的两个关键点, 递归终止条件：只有一个盘子时, 递归表达式：要找出递归表达式,
即：
可以移动。
可以如下设想:
3编程思路
首先，要找出递归的两个关键点, 递归终止条件：只有一个盘子时, 递归表达式：要找出递归表达式,
第一步：将64个盘子的问题简化
(3)
最后
将63
先将 上面 的-63
第二步，将63个盘子的问题简化 成62个盘子的问题，同样分3
再将62个盘子的
问题简化成61个
下面以3个盘子为例说明详细的移动过程：
⑴ 将座A上的2个盘子移动到座B上;
⑵ 将座A上的1个盘子移动到座C上;
⑶ 将座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可以描述为：
（1） 将n-1个盘子从座A借助座C移到座B;
（2） 将剩下的一个盘子从座A移到座C;
（3） 将n-1个盘子从座B借助座A移到座C;
开1
: ►
HN函数
1
F
4
►
“请输入盘子
继 续 运 行
Sca nf(%d
^调用
/显示盘子的
N递
*
f(n=
Printf(
；
函数 HN(int n,char a,char b,char c) 表示将 n
个盘子从座A移到座C,移动过程中借助B
关键语句：HN( n-1,a,c,b)；
prin tf("from %c to %c\n",a,c)
HN(n-1,b,a,c);
假设盘子数为2、5,则其运行过程
为:
■i*on
n
to
c
■Fom
A
to
B
■von
C
to
B
:t*on
n
to
C