Problem 2063 --算法3-5:n阶Hanoi塔问题

2063: 算法3-5:n阶Hanoi塔问题

"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $20$ 正确数量 $9$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签 递推
假设有三个分别命名为X、Y和Z的塔座,在塔座X上插有n个直径大小各不相同、依小到大编号为1,2,...,n的圆盘。现要求将X轴上的n个圆盘移至塔座Z上并仍按同样顺序叠排,圆盘移动时必须遵循下列规则:
1)每次只能移动一个圆盘;
2)圆盘可以插在X、Y和Z中的任一塔座上;
3)任何时刻都不能将一个较大的圆盘压在较小的圆盘之上。
如何实现移动圆盘的操作呢?当n=1时,问题比较简单,只要将编号为1的圆盘从塔座X直接移至塔座Z上即可;当n>1时,需利用塔座Y作辅助塔座,若能设法将压在编号为n的圆盘之上的n-1个圆盘从塔座X(依照上述法则)移至塔座Y上,则可先将编号为n的圆盘从塔座X移至塔座Z上,然后再将塔座Y上的n-1个圆盘(依照上述法则)移至塔座Z上。而如何将n-1个圆盘从一个塔座移至另一个塔座的问题是一个和原问题具有相同特征属性的问题,只是问题的规模小1,因此可以用同样的方法求解。由此可得如下图算法所示的求解n阶Hanoi塔问题的C函数。
图:求解n阶Hanoi塔问题的C函数
现在就请你将上述算法实现吧。

输入数据有多组,每组1个整数n,表示Hanoi塔的阶数。

将每次移动(move)按照以下格式输出:%2d. Move disk %d from %c to %c\n
上述格式中第一个整数表示第几次移动,第二个整数表示移动第几个圆盘,后两个字符表示将圆盘从哪个塔座移至哪个塔座上。每组输出后面输出一个空行。

1
2
3
 1. Move disk 1 from X to Z

 1. Move disk 1 from X to Y
 2. Move disk 2 from X to Z
 3. Move disk 1 from Y to Z

 1. Move disk 1 from X to Z
 2. Move disk 2 from X to Y
 3. Move disk 1 from Z to Y
 4. Move disk 3 from X to Z
 5. Move disk 1 from Y to X
 6. Move disk 2 from Y to Z
 7. Move disk 1 from X to Z
提示:
1、算法描述中输出使用的是%i,实际上就是使用%d。
2、输出时移动次数是两位的,我们保证输入量不会太大。
3、如果使用全局变量来记录移动的次数,注意每次在进行一个新的一组测试时,需要将这个全局计数变量设为0。
总结:
Hanoi塔(汉诺塔)是一个典型的利用递归解决的问题。如果你对迭代(循环)更有偏好,不妨用迭代来实现试试。

推荐代码 查看2063 所有题解 上传题解视频得图灵币

本题记录 用 户(点击查看用户) 运行号(点击购买题解) 时 间
算法最快[$0 $ms] sqrjy 607573 2020-07-17 11:03:10
内存最少[$944 $KB] 范晋豪@信息与计算科学142 152679 2017-11-16 15:10:13
第一AC 范晋豪@信息与计算科学142 152678 2017-11-16 15:10:13
第一挑战 范晋豪@信息与计算科学142 152678 2017-11-16 15:10:13

赛题来源/所属竞赛 数据结构高分笔记 数据结构高分笔记

竞赛编号 竞赛名称 竞赛时间 访问比赛