李遠哲 高世樂

摘? ?要：遞推是研究算法和編程的重要內(nèi)容，傳統(tǒng)謎題有著受眾廣、社會影響力大的特征，主要探討遞推關(guān)系的謎題更具特色。文章以受限的漢諾塔、Reve謎題和安全開關(guān)謎題為例，來探討遞推關(guān)系及其顯式公式，以期對計算機專業(yè)師生學習遞推關(guān)系的研究有所啟發(fā)。

關(guān)鍵詞：遞推關(guān)系;受限的漢諾塔;Reve謎題;安全開關(guān)謎題

對于計算機相關(guān)專業(yè)的師生來說，發(fā)現(xiàn)遞推關(guān)系是很重要的一項基本功，若能更進一步地給出顯式公式，就意味著問題的完滿解決，既可以分析問題的時空復雜度，又可以想辦法枚舉可行解。初識遞推關(guān)系，有幾個小例子是各種教科書重點介紹、師生都非常熟悉的，比如：n！ = n*（n-1）！，斐波那契序列Fn = Fn-1+Fn-2，楊輝三角形c（n， k） = c（n-1， k-1） + c（n-1， k）等。本文主要探討漢諾塔問題的變種及相關(guān)謎題，漢諾塔問題是一個古老的謎題，相當長時間里一直牽動著大家的注意力，原因有以下兩點：（1）其遞推關(guān)系簡單，F(xiàn)n = 2Fn-1+1，閉形式也簡單，F(xiàn)n = 2n-1。（2）有許多變種謎題及相似謎題。本文主要介紹兩種漢諾塔問題的變種以及一種相類似的謎題，通過謎題一起欣賞、學習遞推關(guān)系，探討遞推的解法，發(fā)掘古老謎題的獨特魅力。

1? ? 受限的漢諾塔謎題

受限的漢諾塔謎題是對漢諾塔問題加以限制的結(jié)果，其移動次數(shù)隨著限制條件的增多而增加。

1.1? 謎題描述

n個大小不同的盤子和3根柱子A，B，C，初始狀態(tài)是所有盤子都在A柱上，按從大到小順序排列，大的在下邊，小的在上邊?，F(xiàn)要將所有盤子移到第3根柱子C上去，要求一次只能移動一個盤子，而且大的不能放到小的上面，這就是普通的漢諾塔問題。受限的漢諾塔謎題是指每次移動要么往中間的B柱上面放置一個盤子，要么從B柱取走一個盤子，即不允許在A與C兩柱之間直接移動盤子。該謎題最早在1944年Scorer等[1]發(fā)表的論文中出現(xiàn)。

1.2? 遞推關(guān)系

當n=1時，從A移一個盤子到B，再從B把該盤子移動到C即可，F(xiàn)1=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，F(xiàn)1=2。

1.3? 顯式公式

遞推關(guān)系為常系數(shù)線性非齊次遞推關(guān)系，可以用標準的解法來解[2]，考慮到后邊的非齊次部分為常數(shù)，可以通過比較簡單的代入法來解：

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

可以證明該步數(shù)為最少移動步數(shù)。Fn依次為 2，8，26，80等?？梢娛芟薜臐h諾塔問題的難度從2n-1提升為3n-1，究其原因就是增加了限制。

2? ? Reve謎題

Reve問題是從另一個方向?qū)h諾塔問題進行調(diào)整改變而形成的。將漢諾塔問題的條件進行適當?shù)胤艑挘?個塔柱擴充為4個塔柱，隨著條件的放寬，其移動次數(shù)將大幅減少。

2.1? 謎題描述

n個大小不同的圓盤和4根木樁A，B，C，D，開始圓盤都在木樁A上，從上到下按從小到大順序排列。目的是通過一系列的移動，將所有的圓盤移到D柱上，要求一次只能移動一個盤子，而且大的不能放到小的上面。假如n=8，需要多少次移動？該謎題首次出現(xiàn)在Henry E. Dudeney[3]的名作The Canterbury Puzzle中。

2.2? 遞推關(guān)系

遞推關(guān)系比較復雜，本文力圖找到與漢諾塔類似的解決辦法，希望找到相似的遞推關(guān)系。當n>2時，充分利用所有的（4根）木樁，先把n個盤子分為k和n-k兩部分，上部為k個小的，下邊為n-k個較大的。先把k個盤子借助于C和D，從A柱移到B柱上面來，這本身是Fk;接下去再把下邊的n-k個借助C從A移到D上，此時B柱由于放有k個小盤子而不可用，問題回到普通的漢諾塔，問題的規(guī)模為n-k，因此步數(shù)為Hn-k;最后把B上的K個借助A和C移動到D上去，這又是Fk。至此，似乎得到了遞推關(guān)系：

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

存在一個重要的問題沒有解決：K是變動的，需要使得Fn達到最小的那個k，因此Fn要從較小的n遞推到較大的n才是合情合理的。

接下來就結(jié)合遞推公式研究k的選取問題。初值為F1 = 1，F(xiàn)2 =3。小規(guī)模問題的探討如表1所示，n為待解決問題的規(guī)模，k為分割參數(shù)的選取值，對應特定的k第3欄為移動次數(shù)Fn的值;表1中帶下劃線部分為最優(yōu)解。

至此發(fā)現(xiàn)，遞推關(guān)系為Fn=min（2Fk+2n-k-1），其中n>2，1≤k

2.3? 擴展討論

從表1可知，F(xiàn)n的序列如下：1， 2， 5， 9， 13， 17， 25， 33， ……。當n=8時，對F8而言，有多種方法可以在33次操作內(nèi)完成圓盤的移動，同時在算法的每次迭代中可以使用k=n/2這個不變的策略。對于普通的n就沒有那么幸運了，亨利杜德尼在他的《坎特伯雷謎題》中分別給出了n=8，n=10，n=21時的解決方案[3]。后來不少學者針對分割參數(shù)k的優(yōu)化展開研究，也得到了部分成果，但還沒有被普遍證實，因此，分割參數(shù)k的選擇仍是一個熱點問題，這就造成Reve問題的顯式公式至今也沒人能夠給出。漢諾塔、受限的漢諾塔、Reve問題表面看起來很相似，但前兩者無論是遞推關(guān)系還是顯式公式都已經(jīng)完美解決，Reve問題卻恰恰相反，僅給出一些小規(guī)模問題的解，也充分說明了算法研究和謎題研究的魅力所在。

3? ? 安全開關(guān)謎題

3.1? 謎題描述

一排n個安全開關(guān)，控制一處軍事設(shè)施的入口?？梢詫﹂_關(guān)進行以下操作：（1）最右邊的開關(guān)隨意開閉。（2）其他開關(guān)開閉的條件是：右側(cè)緊鄰的為開，右側(cè)其他的為關(guān)。（3）每次只能操作一個開關(guān)。初始狀態(tài)為全開，終態(tài)目標為全關(guān)。求出最少開閉次數(shù)。該謎題最初由Greenes[4]提出。

3.2? 遞推關(guān)系

先研究幾個最小的實例（見表2）。想關(guān)閉最左邊的開關(guān)，所有開關(guān)的狀態(tài)一定是“110…0”，因此，關(guān)閉最左開關(guān)前一定要先關(guān)閉右側(cè)的n-2個，也就是要對右側(cè)的n-2個做同樣的操作，這是Fn-2;接下來可以操作第一個開關(guān)并得到新狀態(tài)“010…0”。在關(guān)閉第二個開關(guān)之前，需要第二個之后的所有開關(guān)為“開”，由于“開”和“關(guān)”為互逆操作，因此將右側(cè)n-2個全部打開需要Fn-2次操作。再接下來，面對的是規(guī)模為n-1的同樣的問題，需要Fn-1次操作。因此，遞推關(guān)系為：

Fn=Fn-2+1+Fn-2+Fn-1=Fn-1+2Fn-2+1，F(xiàn)1=1，F(xiàn)2=2。

3.3? 顯式公式

由遞推關(guān)系得出，特征方程為r2-r+2=0，特征根為r1=2，r2=-1;對應的齊次線性遞推關(guān)系的通解為Fn=α1（2）n+α2（-1）n;由于遞推關(guān)系Fn=Fn-1+2Fn-2+1非齊次部分為常數(shù)，故特解形如常數(shù)c，代入遞推關(guān)系得c=c+2c+1，解得c=-1/2。

因此本問題的通解形如Fn=α1（2）n+α2（-1）n-1/2，把初值F1=1，F(xiàn)2=2代入，解得α1=2/3，α2=-1/6。

至此，顯式公式為：Fn=2/3（2）n-1/6（-1）n-1/2，n≥1。當n為奇數(shù)時，該公式可以得到簡化Fn=（2n+1-1）/3;當n為偶數(shù)時，該公式可以得到簡化Fn=（2n+1-2）/3。

4? ? 結(jié)語

經(jīng)典謎題浩如煙海，遞推關(guān)系魅力無窮，將二者結(jié)合，主要以遞推關(guān)系及其求解為切入點，立足于計算機專業(yè)師生，對3個經(jīng)典謎題進行探討。其中受限的漢諾塔和安全開關(guān)問題已經(jīng)完滿解決，其遞推關(guān)系清晰，顯式公式明確。與漢諾塔問題及受限的漢諾塔問題題面非常類似的Reve問題卻比以上兩個謎題更難，其遞推關(guān)系中存在待定參數(shù)，顯式公式目前更是不能給出，有待于進一步研究。

探討更多的謎題、研究更多的遞推關(guān)系，不失為一種學習算法和編程的好方法，既具有趣味性，又有一定的挑戰(zhàn)性，算法不只是天才的游戲，都可以試一試。

[參考文獻]

[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