1 / 6
文档名称:

汉诺塔问题的非递归新解法.doc

格式:doc   页数:6页
下载后只包含 1 个 DOC 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

汉诺塔问题的非递归新解法.doc

上传人:xxj16588 2016/7/24 文件大小:0 KB

下载得到文件列表

汉诺塔问题的非递归新解法.doc

相关文档

文档介绍

文档介绍:汉诺塔问题的非递归算法计算机科学与技术学院计 11-1 班张春颖( 组长)37号刘丹( 组员)22号汉诺塔问题的非递归新解法计 11-1 张春颖 37号刘丹 22号摘要:汉诺塔问题是计算机算法设计中经常被大家引用来说明递归算法的一个经典问题,长期以来,很多人一直认为这个问题只能用递归方法求解,从讨论汉诺塔问题的几个基本特性入手,通过分析和归纳总结, 提出了一种全新的解决汉诺塔问题的简洁而又高效的非递归解法,并用具体的实例对其进行了验证。关键词:汉诺塔;非递归;对称性;形式不变性一. 汉诺塔问题及其特性汉诺塔问题可以一般地表述为:有3 根针 A,B,C, 在A 针上有 n 个大小互不相同的盘子, 大盘在下, 小盘在上, 现在要将这 n 个盘子全部移到 C 针上, 规则是: 每次只能移一个盘子, 任何时候在每根针上都要保持大盘在下面小盘在上; 移动过程可以利用针 B. 请问该怎么移? 汉诺塔问题是一个古典的数学问题, 一般的参考文献中都认为汉诺塔问题是一个只能用递归方法解决的问题。汉诺塔问题具有递归性, 但并不是说它就只能用递归方法来解决, 为了寻求其非递归新解法,下面先来讨论一下汉诺塔问题的几个基本特性。 1. 汉诺塔问题的递归性将这 n 个盘子由小到大依次编号为: 1,2,3,......N. 为了将这 n 个盘子按照规则从针 A 移动到针 C. 可以分 3 步走: 第1 步:将前 n-1 个盘子按照规则从针 A 移动到针 B; 第2 步:将第 n 个盘子直接从针 A 移动到针 C; 第3 步:将前 n-1 个盘子按照规则从针 B 移动到针 C; 这样一来,n 个盘子的汉诺塔问题就转化成了 n-1 个盘子的汉诺塔问题, 而它们之间只是盘子的数目以及起点和终点有别而已。而 n-1 个盘子的汉诺塔问题又可以进一步地转化成 n-2 个盘子的汉诺塔问题。如此转化下去,最终结果是: n 个盘子的汉诺塔问题转化成了一序列 1 个盘子的汉诺塔问题。 2 汉诺塔问题的对称性由上述分析可见,n 个盘子的汉诺塔问题可以转化为两个 n-1 个盘子的汉诺塔问题和一个1 个盘子的汉诺塔问题, 并且这 1 个盘子的汉诺塔问题正好处于那两个 n-1 个盘子的汉诺塔问题的中间, 因此, 解决 n 个盘子的汉诺塔问题所需要的最少操作步数应该是奇数, 而且所有操作步的操作对象按照顺序应该是中心对称的,对称中心就是 N 号盘。 3. 汉诺塔问题的形式不变性一般地,设 X,Y,Z 为3 根针,S 为将 n 个盘子按照给定的规则从针 X 移到针 Y 所需的所有操作步的集合, 如果用 A,B,C 的任意一个全排列 K1, K2, K3 去对应替换 S 中的 X,Y,Z:K 1 替换 X,K2 替换 Y,K3 替换 Z, 则得到的是将 n 个盘子按照同样的规则从针 K1 移到 K2 所需的所有操作步集合。 4. 汉诺塔问题的轮换性设S 为将 n 个盘子按照给定的规则从针 A 移到针 B 所需的所有操作步的集合,按照形式不变性, 如果将 S 中的 A 全部换成 B,B 全部换成 C,C 全部换成 A, 则得到的是将 N 个盘子按照同样的规则从针 B 移到针 C 所需的所有操作步的集合。同样, 如果将 S 中的 A 全部换成 C,C 全部换成 A,B 保持不变, 则得到的是将 n 个盘子按照同样的规