經(jīng)典謎題中的遞推關(guān)系及其求解研究

李遠(yuǎn)哲 高世樂

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

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

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

1? ? 受限的漢諾塔謎題

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

1.1? 謎題描述

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

1.2? 遞推關(guān)系

當(dāng)n=1時(shí)，從A移一個(gè)盤子到B，再從B把該盤子移動(dòng)到C即可，F(xiàn)1=2。如果n>1，則問題分以下幾步：（1）先以B為過渡，把n-1個(gè)盤子從A移到C，即Fn-1。（2）把最大的盤子從A移到B。（3）以B為過渡，把C上的n-1個(gè)盤子移到A上，又一個(gè)Fn-1。（4）將B上的最大的盤子移到C上。（5）通過B柱，遞歸地將n-1個(gè)盤子從A移到C上，第3個(gè)Fn-1。

綜合以上5步得出：Fn=3Fn-1+2，F(xiàn)1=2。

1.3? 顯式公式

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

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

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

2? ? Reve謎題

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

2.1? 謎題描述

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

2.2? 遞推關(guān)系

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

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

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

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

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

2.3? 擴(kuò)展討論

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

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

3.1? 謎題描述

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

3.2? 遞推關(guān)系

先研究幾個(gè)最小的實(shí)例（見表2）。想關(guān)閉最左邊的開關(guān)，所有開關(guān)的狀態(tài)一定是“110…0”，因此，關(guān)閉最左開關(guān)前一定要先關(guān)閉右側(cè)的n-2個(gè)，也就是要對(duì)右側(cè)的n-2個(gè)做同樣的操作，這是Fn-2;接下來可以操作第一個(gè)開關(guān)并得到新狀態(tài)“010…0”。在關(guān)閉第二個(gè)開關(guān)之前，需要第二個(gè)之后的所有開關(guān)為“開”，由于“開”和“關(guān)”為互逆操作，因此將右側(cè)n-2個(gè)全部打開需要Fn-2次操作。再接下來，面對(duì)的是規(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;對(duì)應(yīng)的齊次線性遞推關(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。當(dāng)n為奇數(shù)時(shí)，該公式可以得到簡(jiǎn)化Fn=（2n+1-1）/3;當(dāng)n為偶數(shù)時(shí)，該公式可以得到簡(jiǎn)化Fn=（2n+1-2）/3。

4? ? 結(jié)語

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

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

[參考文獻(xià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