經典謎題中的遞推關系及其求解研究

李遠哲 高世樂

摘? ?要：遞推是研究算法和編程的重要內容，傳統謎題有著受眾廣、社會影響力大的特征，主要探討遞推關系的謎題更具特色。文章以受限的漢諾塔、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柱上，按從大到小順序排列，大的在下邊，小的在上邊?，F要將所有盤子移到第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等?？梢娛芟薜臐h諾塔問題的難度從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