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

汉诺塔问题的非递归算法
计算机科学与技术学院
计11-1 班
张春颖(组长) 37 号
刘丹(组员) 22 号
汉诺塔问题的非递归新解法

计11-1 张春颖 37号
刘丹 22号
摘要:汉诺塔问题是计算机算法设计中经常被大家引用来说明递归算法的一个经典问题,长期以来,很多人一直认为这个问题只能用递归方法求解,从讨论汉诺塔问题的几个基本特性入手,通过分析和归纳总结,提出了一种全新的解决汉诺塔问题的简洁而又高效的非递归解法,并用具体的实例对其进行了验证。
关键词:汉诺塔;非递归;对称性;形式不变性
汉诺塔问题及其特性
汉诺塔问题可以一般地表述为:有3根针A,B,C,在A针上有n个大小互不相同的盘子,大盘在下,小盘在上,现在要将这n个盘子全部移到C针上,规则是:每次只能移一个盘子,任何时候在每根针上都要保持大盘在下面小盘在上;?
汉诺塔问题是一个古典的数学问题,一般的参考文献中都认为汉诺塔问题是一个只能用递归方法解决的问题。
汉诺塔问题具有递归性,但并不是说它就只能用递归方法来解决,为了寻求其非递归新解法,下面先来讨论一下汉诺塔问题的几个基本特性。
汉诺塔问题的递归性
将这n个盘子由小到大依次编号为:1,2,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号盘。

一般地,设X,Y,Z为3根针,S为将n个盘子按照给定的规则从针X移到针Y所需的所有操作步的集合,如果用A,B,C的任意一个全排列K1,K2,K3去对应替换S中的X,Y,Z:K1替换X,K2替换Y,K3替换Z,则得到的是将n个盘子按照同样的规则从针K1移到K2所需的所有操作步集合。
汉诺塔问题的轮换性
设S为将n个盘子按照给定的规则从针A移到针B所需的所有操作步的集合,按照形式不变性,如果将S中的A全部换成B,B全部换成C,C全部换成A,则得到的是将N个盘子按照同样的规则从针B移到针C所需的所有操作步的集合。同样,如果将S中的A全部换成C,C全部换成A,B保持不变,则得到的是将n个盘子按照同样的规则从针C移到针B所需的所有操作步的集合。
递归算法如下
Void hanoi(int n,char x,char y,char z)上按
//将塔座x上按直径由小到大且自上而下编号为1至nde 个圆盘按规则搬到塔