李远哲 高世乐

摘   要：递推是研究算法和编程的重要内容，传统谜题有着受众广、社会影响力大的特征，主要探讨递推关系的谜题更具特色。文章以受限的汉诺塔、Reve谜题和安全开关谜题为例，来探讨递推关系及其显式公式，以期对计算机专业师生学习递推关系的研究有所启发。

关键词：递推关系;受限的汉诺塔;Reve谜题;安全开关谜题

对于计算机相关专业的师生来说，发现递推关系是很重要的一项基本功，若能更进一步地给出显式公式，就意味着问题的完满解决，既可以分析问题的时空复杂度，又可以想办法枚举可行解。初识递推关系，有几个小例子是各种教科书重点介绍、师生都非常熟悉的，比如：n！ = n*（n-1）！，斐波那契序列Fn = Fn-1+Fn-2，杨辉三角形c（n， k） = c（n-1， k-1） + c（n-1， k）等。本文主要探讨汉诺塔问题的变种及相关谜题，汉诺塔问题是一个古老的谜题，相当长时间里一直牵动着大家的注意力，原因有以下两点：（1）其递推关系简单，Fn = 2Fn-1+1，闭形式也简单，Fn = 2n-1。（2）有许多变种谜题及相似谜题。本文主要介绍两种汉诺塔问题的变种以及一种相类似的谜题，通过谜题一起欣赏、学习递推关系，探讨递推的解法，发掘古老谜题的独特魅力。

1    受限的汉诺塔谜题

受限的汉诺塔谜题是对汉诺塔问题加以限制的结果，其移动次数随着限制条件的增多而增加。

1.1  谜题描述

n个大小不同的盘子和3根柱子A，B，C，初始状态是所有盘子都在A柱上，按从大到小顺序排列，大的在下边，小的在上边。现要将所有盘子移到第3根柱子C上去，要求一次只能移动一个盘子，而且大的不能放到小的上面，这就是普通的汉诺塔问题。受限的汉诺塔谜题是指每次移动要么往中间的B柱上面放置一个盘子，要么从B柱取走一个盘子，即不允许在A与C两柱之间直接移动盘子。该谜题最早在1944年Scorer等[1]发表的论文中出现。

1.2  递推关系

当n=1时，从A移一个盘子到B，再从B把该盘子移动到C即可，F1=2。如果n>1，则问题分以下几步：（1）先以B为过渡，把n-1个盘子从A移到C，即Fn-1。（2）把最大的盘子从A移到B。（3）以B为过渡，把C上的n-1个盘子移到A上，又一个Fn-1。（4）将B上的最大的盘子移到C上。（5）通过B柱，递归地将n-1个盘子从A移到C上，第3个Fn-1。

综合以上5步得出：Fn=3Fn-1+2，F1=2。

1.3  显式公式

递推关系为常系数线性非齐次递推关系，可以用标准的解法来解[2]，考虑到后边的非齐次部分为常数，可以通过比较简单的代入法来解：

Fn=3Fn-1+2=3（Fn-2+2）+2=3[（Fn-3+2）+2]=……=F1×3n-1 +3n-1-1=3n-1。

可以证明该步数为最少移动步数。Fn依次为 2，8，26，80等。可见受限的汉诺塔问题的难度从2n-1提升为3n-1，究其原因就是增加了限制。

2    Reve谜题

Reve问题是从另一个方向对汉诺塔问题进行调整改变而形成的。将汉诺塔问题的条件进行适当地放宽，把3个塔柱扩充为4个塔柱，随着条件的放宽，其移动次数将大幅减少。

2.1  谜题描述

n个大小不同的圆盘和4根木桩A，B，C，D，开始圆盘都在木桩A上，从上到下按从小到大顺序排列。目的是通过一系列的移动，将所有的圆盘移到D柱上，要求一次只能移动一个盘子，而且大的不能放到小的上面。假如n=8，需要多少次移动？该谜题首次出现在Henry E. Dudeney[3]的名作The Canterbury Puzzle中。

2.2  递推关系

递推关系比较复杂，本文力图找到与汉诺塔类似的解决办法，希望找到相似的递推关系。当n>2时，充分利用所有的（4根）木桩，先把n个盘子分为k和n-k两部分，上部为k个小的，下边为n-k个较大的。先把k个盘子借助于C和D，从A柱移到B柱上面来，这本身是Fk;接下去再把下边的n-k个借助C从A移到D上，此时B柱由于放有k个小盘子而不可用，问题回到普通的汉诺塔，问题的规模为n-k，因此步数为Hn-k;最后把B上的K个借助A和C移动到D上去，这又是Fk。至此，似乎得到了递推关系：

Fn = Fk + Hn-k + Fk = 2Fk + Hn-k = 2Fk + 2n-k -1

存在一个重要的问题没有解决：K是变动的，需要使得Fn达到最小的那个k，因此Fn要从较小的n递推到较大的n才是合情合理的。

接下来就结合递推公式研究k的选取问题。初值为F1 = 1，F2 =3。小規模问题的探讨如表1所示，n为待解决问题的规模，k为分割参数的选取值，对应特定的k第3栏为移动次数Fn的值;表1中带下划线部分为最优解。

至此发现，递推关系为Fn=min（2Fk+2n-k-1），其中n>2，1≤k

2.3  扩展讨论

从表1可知，Fn的序列如下：1， 2， 5， 9， 13， 17， 25， 33， ……。当n=8时，对F8而言，有多种方法可以在33次操作内完成圆盘的移动，同时在算法的每次迭代中可以使用k=n/2这个不变的策略。对于普通的n就没有那么幸运了，亨利杜德尼在他的《坎特伯雷谜题》中分别给出了n=8，n=10，n=21时的解决方案[3]。后来不少学者针对分割参数k的优化展开研究，也得到了部分成果，但还没有被普遍证实，因此，分割参数k的选择仍是一个热点问题，这就造成Reve问题的显式公式至今也没人能够给出。汉诺塔、受限的汉诺塔、Reve问题表面看起来很相似，但前两者无论是递推关系还是显式公式都已经完美解决，Reve问题却恰恰相反，仅给出一些小规模问题的解，也充分说明了算法研究和谜题研究的魅力所在。

3    安全開关谜题

3.1  谜题描述

一排n个安全开关，控制一处军事设施的入口。可以对开关进行以下操作：（1）最右边的开关随意开闭。（2）其他开关开闭的条件是：右侧紧邻的为开，右侧其他的为关。（3）每次只能操作一个开关。初始状态为全开，终态目标为全关。求出最少开闭次数。该谜题最初由Greenes[4]提出。

3.2  递推关系

先研究几个最小的实例（见表2）。想关闭最左边的开关，所有开关的状态一定是“110…0”，因此，关闭最左开关前一定要先关闭右侧的n-2个，也就是要对右侧的n-2个做同样的操作，这是Fn-2;接下来可以操作第一个开关并得到新状态“010…0”。在关闭第二个开关之前，需要第二个之后的所有开关为“开”，由于“开”和“关”为互逆操作，因此将右侧n-2个全部打开需要Fn-2次操作。再接下来，面对的是规模为n-1的同样的问题，需要Fn-1次操作。因此，递推关系为：

Fn=Fn-2+1+Fn-2+Fn-1=Fn-1+2Fn-2+1，F1=1，F2=2。

3.3  显式公式

由递推关系得出，特征方程为r2-r+2=0，特征根为r1=2，r2=-1;对应的齐次线性递推关系的通解为Fn=α1（2）n+α2（-1）n;由于递推关系Fn=Fn-1+2Fn-2+1非齐次部分为常数，故特解形如常数c，代入递推关系得c=c+2c+1，解得c=-1/2。

因此本问题的通解形如Fn=α1（2）n+α2（-1）n-1/2，把初值F1=1，F2=2代入，解得α1=2/3，α2=-1/6。

至此，显式公式为：Fn=2/3（2）n-1/6（-1）n-1/2，n≥1。当n为奇数时，该公式可以得到简化Fn=（2n+1-1）/3;当n为偶数时，该公式可以得到简化Fn=（2n+1-2）/3。

4    结语

经典谜题浩如烟海，递推关系魅力无穷，将二者结合，主要以递推关系及其求解为切入点，立足于计算机专业师生，对3个经典谜题进行探讨。其中受限的汉诺塔和安全开关问题已经完满解决，其递推关系清晰，显式公式明确。与汉诺塔问题及受限的汉诺塔问题题面非常类似的Reve问题却比以上两个谜题更难，其递推关系中存在待定参数，显式公式目前更是不能给出，有待于进一步研究。

探讨更多的谜题、研究更多的递推关系，不失为一种学习算法和编程的好方法，既具有趣味性，又有一定的挑战性，算法不只是天才的游戏，都可以试一试。

[参考文献]

[1]SCORER R S，GRUNDY P M，SMITH C A B.Some binary games[J].Mathematical Gazette，1944（28）：96-103.

[2]ROSEN，KENNETH H.Discrete mathematics and its applications[M].New York：McGraw-Hill Science/Engineering/Math，2007.

[3]DUDENEY H E.Canterbury puzzles and other curious problems[J].Tredition Classics，2013（5）：55-56.

[4]GREENES C E.Function generating problems：the row chip switch[J].Arithmetic Teacher，1973（20）：545-549.

Study on recurrence relations in classical puzzles and their solutions

Li Yuanzhe1， Gao Shile2*

（1.School of Computer Science， Southwest Petroleum University， Chengdu 610500， China;

2.School of Business Administration， Huaqiao University， Quanzhou 362021， China）

Abstract：Recurrence relation is an important part of research on algorithm and programming. Traditional puzzles have the characteristics of wide audiences and great social influence. Those puzzles which mainly discuss recurrence relations have more characteristics. This paper takes the restricted Hanoi Tower， Reve puzzle and safety switch puzzle as an examples to discuss the recurrence relation and its closed form-formula， in order to inspire the computer professional teachers and students to learn the recurrence relations.

Key words：recurrence relation; restricted Hanoi Tower; Reve puzzle; safety switch puzzle