严海兵

（苏州科技大学 图书馆，江苏 苏州 215009）

汉诺塔问题源于古印度的一个游戏。游戏中有A、B、C三根柱子，A柱上从下往上按照大小顺序摞着n个圆盘。游戏的目的：把圆盘按大小顺序重新摆放到C柱上。规则为：（1）一次只能移动一只圆盘；（2）每根柱子只有最上面的圆盘可以搬动；（3）小圆盘上不能摆放大圆盘；（4）移动圆盘时可以利用B柱当作过渡柱子。

一些文献在介绍递归算法、借助堆栈转化递归算法为非递归算法等内容时往往引入汉诺塔问题作为典型实例介绍[1－2]。一些学者在提出新的程序算法思路时，也常用汉诺塔问题的解决作为验证实例。如文献[3]利用二叉树的中序遍历深入理解程序递归算法；文献[4]利用状态机的思想提出的非递归算法，避免堆栈内存溢出问题；文献[5-7]化解汉诺塔问题为抽象分层树，利用树分层次迭代的非递归算法；文献[8]利用人工智能算法中的启发式搜索，解决汉诺塔问题，尝试A算法的执行效率。

笔者通过对汉诺塔圆盘搬运过程的分析，改变传统的圆盘编码从上到下、由小到大的顺序1，2，…，n，为逆序n，n-1，…，1，通过找出圆盘移动的数学规律，提出一种新的简洁高效的非递归算法。图1为汉诺塔的圆盘顺序、逆序编码图。下文分析中所涉及的圆盘编码均按逆序编码。

图1 汉诺塔的圆盘顺序、逆序编码图

1 圆盘搬运的数学规律

汉诺塔上的圆盘按照从大到小的顺序编号1，2，…，n。当n=1时，圆盘搬运顺序为，1 A→C；当n=2时，圆盘搬运顺序为，2 A→B、1 A→C、2 B→C；当n=3时，圆盘搬运顺序见表1；当n=4时，圆盘搬运顺序见表2。……