“唔……你下午沒(méi)有課嗎？”小P推門走進(jìn)教研室，他剛剛上完數(shù)理統(tǒng)計(jì)，又沒(méi)有約好踢球，于是決定到教研室晃晃，一進(jìn)門就看到老C趴在桌子上不知在搗鼓什么。
“嗯，我下午沒(méi)有課……我在研究怎么破解人類的tower rush……這個(gè)真是游戲的bug，暴雪一定會(huì)做出平衡的……”老C被小P的tower rush打得很郁悶，于是在網(wǎng)上找找對(duì)策。
“呵呵，呵呵，”小P笑道，“我們總會(huì)找到游戲中的不平衡點(diǎn)加以利用的……”他搖搖頭，“說(shuō)到游戲，我突然想到你上次說(shuō)小朋友吃蘋果的游戲，怎么可以用一個(gè)循環(huán)左移實(shí)現(xiàn)呢？”
“哦，是的是的……”老C關(guān)掉那些無(wú)聊的網(wǎng)頁(yè)，“你不提，我還真是險(xiǎn)些忘了。”他接著說(shuō)道，“關(guān)于這個(gè)問(wèn)題，它的前提條件是每數(shù)到2的小朋友被踢出，這個(gè)
會(huì)是你在各大面試筆試中會(huì)常遇到的……”說(shuō)完他指揮小P拉過(guò)白板，“這樣其實(shí)相當(dāng)于求解一個(gè)2進(jìn)制數(shù)的循環(huán)左移結(jié)果。”
“哦？那么是怎么來(lái)的呢？”小P問(wèn)道。
“同樣，由于我們的智力有限，無(wú)法理解過(guò)于復(fù)雜的問(wèn)題，所以我們先來(lái)看看幾個(gè)實(shí)際的例子。”老C說(shuō)道，說(shuō)著他在白板上畫了一個(gè)圈，然后在上面按順時(shí)針?lè)较驈?標(biāo)到6。“我們來(lái)看看會(huì)發(fā)生什么……”老C說(shuō)道，然后開始在白板上比劃起來(lái)。
“看看，我們玩過(guò)一輪后，出現(xiàn)了這種情況……”老C把開始的情況和玩過(guò)一輪后的情況寫了下來(lái)。
“小圓圈內(nèi)的數(shù)字表示座位號(hào)，”老C解釋。“看看我們可以得到一些什么又用的結(jié)果。”看到小P莫名其妙的樣子，老C接著說(shuō)道，“好吧，我們令T(n)表示
n個(gè)小朋友結(jié)束游戲后，剩下的小朋友的座位號(hào)碼，我們發(fā)現(xiàn)，當(dāng)6個(gè)小朋友玩這個(gè)游戲1輪后，還剩下3個(gè)小朋友依照同樣的方式再繼續(xù)玩。”老C看到小P還是
懵懂的樣子，強(qiáng)調(diào)道，“注意，在這里我們發(fā)現(xiàn)剩下的3個(gè)小朋友需要依照同樣的方式繼續(xù)，這就表明了，其實(shí)這個(gè)問(wèn)題是遞歸的。”
“唔，的確是這樣，這樣，求解6個(gè)小朋友玩游戲的過(guò)程，就變?yōu)榍蠼?個(gè)小朋友玩游戲的過(guò)程了……但是……等等……我發(fā)現(xiàn)好像小朋友編號(hào)的規(guī)則不一樣了……”小P道。
“是么？”老C贊許的點(diǎn)點(diǎn)頭，“你發(fā)現(xiàn)有什么區(qū)別？”
“嗯，原來(lái)的小朋友的編號(hào)是依照座位號(hào)編號(hào)的，但是在進(jìn)行1輪游戲后，剩下的3個(gè)小朋友的編號(hào)方式就不是依照座位編號(hào)了，好像是（2*座位號(hào)-1）？”小P問(wèn)道。
“沒(méi)錯(cuò)，的確是這樣，而這個(gè)就是這個(gè)遞歸問(wèn)題的關(guān)鍵……”老C說(shuō)道，“如果我們令T(n)為n個(gè)小朋友束游戲后，剩下的小朋友的座位號(hào)碼，那么T(n)一定是座位號(hào)碼吧？”
“……”小P無(wú)語(yǔ)點(diǎn)頭。
“但是剩下的3個(gè)小朋友如果繼續(xù)，是不是需按照新的編號(hào)規(guī)律進(jìn)行編碼，才符合我們T(n)表示座位號(hào)的假定？”老C問(wèn)道。
“……”小P搖頭。
“呵呵，”老C笑道，“你可以這樣認(rèn)為。”說(shuō)完他在白板上寫下一行公式。
T(6) = 2 * T(3) – 1
“如果我們要3個(gè)小朋友玩游戲，他們的編號(hào)應(yīng)當(dāng)是1、2、3才對(duì)，但由于實(shí)際上他們的編號(hào)是1、3、5，所以他們的實(shí)際編號(hào)是2*T(3)-1。因?yàn)?
T(3)的假定是小朋友的編號(hào)需要從1開始依次為2、3，玩游戲結(jié)束剩下的那個(gè)小朋友的號(hào)碼，但是實(shí)際上剩下的3個(gè)小朋友的編號(hào)是1、3、5，所以按照這
樣的編號(hào)玩游戲，結(jié)束時(shí)剩下的小朋友的編號(hào)就是2*T(3)-1。”老C笑道，“你仔細(xì)體會(huì)一下就明白了。”
“哦，有些意思……我再看看。”小P說(shuō)道。他想了一會(huì)兒，覺(jué)得也不是很難以想通，于是說(shuō)道，“好吧，那么然后呢？”
“然后我們就可以猜測(cè)這樣的遞推公式。”老C說(shuō)道。
T(n) = 2T(n/2) –
1
“為了好看起見，我們將上面的公式稍微更改一下。”老C又說(shuō)道。
T(2n) = 2T(n) -
1
“這樣我們就有了第一個(gè)遞歸公式。”老C說(shuō)道。
“哦，看來(lái)只對(duì)偶數(shù)個(gè)小朋友起作用……如果小朋友的個(gè)數(shù)是奇數(shù)怎么辦？”小P問(wèn)道。
“同樣，我們也找一個(gè)例子來(lái)研究一下。”老C說(shuō)道。
“同樣，我們把玩過(guò)一輪的情況畫下來(lái)。”老C說(shuō)道。
“與上面分析的道理一樣，我們可以得到T(2n+1)
= 2T(n)+1”老C說(shuō)道，“你再仔細(xì)看看。”
小P低頭想了一會(huì)兒，說(shuō)道：“嗯，沒(méi)有什么難的，這個(gè)我可以理解。”
“好的，這樣我們得到了遞推公式。”老C說(shuō)道，“你可以假定參加游戲的小朋友是2n和2n+1個(gè)，按照類似的辦法，畫個(gè)圖，就會(huì)得到這樣的結(jié)論。”說(shuō)著他在白板上寫下如下公式。
T(1) = 1
T(2n) = 2T(n)-1
T(2n+1) = 2T(n)＋1
“但是這組遞推公式無(wú)法依照我們前面的解法解出來(lái)它的通項(xiàng)，因?yàn)槲覀兒茈y將它轉(zhuǎn)換為一個(gè)求和的方程。”老C說(shuō)道，“在不知道更好的解決方法之前，我們只有拼拼人品，使用數(shù)學(xué)歸納法啦。”
“唔，你是說(shuō)要猜測(cè)出通項(xiàng)公式，然后使用數(shù)學(xué)歸納法證明嗎？”小P問(wèn)道。
“是啊是啊，”老C回答，“你好歹是本科畢業(yè)，這個(gè)應(yīng)當(dāng)難不倒你吧……”
“切，這個(gè)只要高中畢業(yè)就會(huì)了！”小P不屑。
“那好吧，剛好我們有一個(gè)程序可以很快的算出最后剩下小朋友的號(hào)碼，我們就來(lái)列一組表格，看看有什么規(guī)律。”老C說(shuō)道。
于是小P打開他的電腦，開始運(yùn)行前一段時(shí)間自己編寫的程序，搗鼓出來(lái)一個(gè)表格，并畫到了白板上。
|
n
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
13
|
14
|
15
|
16
|
17
|
18
|
19
|
20
|
|
T(n)
|
1
|
1
|
3
|
1
|
3
|
5
|
7
|
1
|
3
|
5
|
7
|
9
|
11
|
13
|
15
|
1
|
3
|
5
|
7
|
9
|
“看看，有什么規(guī)律啊。”小P自言自語(yǔ)，“唔，好像在n = 2m的時(shí)候T(n)=1，而且T(n)會(huì)隨著2m為模，很有規(guī)律的在變化。”
“沒(méi)錯(cuò)，根據(jù)遞推公式，T(2n)=2T(n)-1，可以看出T(2)=1，T(4)=2T(2)-1=1，而T(8)=2T(4)-1=1，以此類推，所以T(2m)=1。”老C補(bǔ)充。
“好像如果n可以寫為n=2m＋k的形式，則T(n)=2k+1。”小P經(jīng)過(guò)一段時(shí)間的觀察，分析道，“這樣我們就可以得到通項(xiàng)公式。”說(shuō)著他在白板上寫下通項(xiàng)。
T(2m+k)=2k+1
“唔，這個(gè)結(jié)論對(duì)不對(duì)呢，我來(lái)用數(shù)學(xué)歸納法證明一下。”小P說(shuō)道。于是他在白板上比劃起來(lái)。
令n = 2m+k，
當(dāng)n = 1時(shí)，m = 0，k = 0
T(1) = 2k + 1 =
1，原式成立。
設(shè)當(dāng)n = 2m +
k時(shí)，T(n) = 2k + 1
那么當(dāng)n = 2m
+ k ＋ 1時(shí)，若n是偶數(shù)，那么k＋1是偶數(shù)，有
T(2n) = 2T(n) –
1
T(2(2m-1+(k+1)/2))
= 2T(2m-1+(k+1)/2) – 1 = 2(2(k+1)/2 + 1)-1 = 2(k+1) -1
等式仍然成立。
若n是奇數(shù)，那么k是偶數(shù)，有
T(2n+1) = 2T(n)
+ 1
T(2(2m-1+k/2)＋1) ＝ 2T(2m-1+k/2) +1 = 2(2k/2+1)
+1 = 2k+3 = 2(k+1) + 1
等式仍然成立。
綜上，原通項(xiàng)成立。
“嗯，看來(lái)我們的猜測(cè)是正確的。”小P道，“但是這個(gè)與循環(huán)左移有什么關(guān)系呢？”
“因?yàn)門(n)會(huì)以2m為模有規(guī)律的變化，這樣促使我們使用2進(jìn)制數(shù)看看有什么有趣的規(guī)律。”老C說(shuō)道。
設(shè)n可以表示為2進(jìn)制數(shù)bmbm-1bm-2…b0，且bk非1即0，則
n = bm2m
+ bm-12m-1 + bm-22m-2 +…+ b0
且bm = 1
那么
k = bm-12m-1
+ bm-22m-2 +…+ b0
2k = bm-12m
+ bm-22m-1 +…+ 2b0
2k + 1 = bm-12m
+ bm-22m-1 +…+ 2b0 + 1 = bm-12m
+ bm-22m-1 +…+ 2b0 + bm
“看看，這就相當(dāng)于對(duì)n的2進(jìn)制數(shù)做了循環(huán)左移一樣！”老C說(shuō)道。
“……”小P低著頭看了半天，“嗯，沒(méi)錯(cuò)，好像是這樣。我們來(lái)帶入幾個(gè)數(shù)值看看吧。”小P把上面幾個(gè)表的數(shù)據(jù)拿來(lái)看看。
5 = (101)2
T(5) = 3 = (11)2
20 = (10100)2
(1001)2
= 9 = T(20)
“唔，看來(lái)確是如此。”小P贊嘆道，“這還真是奇妙的事情。”
“是啊是啊，所以你以后在面試和筆試的時(shí)候，碰到相同的問(wèn)題，就無(wú)需寫出大堆的代碼啦，只要寫一個(gè)實(shí)現(xiàn)循環(huán)左移的函數(shù)就可以了。”老C回答。
“嗯……”小P點(diǎn)點(diǎn)頭，“既然數(shù)到2的小朋友被踢出的結(jié)果可以用一個(gè)循環(huán)左移表示，那么數(shù)到3，數(shù)到4……數(shù)到n被踢出的結(jié)果有什么好的方法表示呢？”小P追問(wèn)。
“呵呵，”老C笑道，“我看到了你光明的未來(lái)……”他點(diǎn)點(diǎn)頭，“這些并沒(méi)有什么現(xiàn)成的結(jié)論，你可以根據(jù)編寫好的程序，自己生成一些數(shù)據(jù)表格，看看有什么特
殊的規(guī)律。我猜如果這些數(shù)字以3為模，可能與3進(jìn)制有關(guān)聯(lián)；如果以4為模，可能和4進(jìn)制有關(guān)……Any
way，你可以進(jìn)行一些嘗試，看能否得出一些有趣的結(jié)論。等你總結(jié)好了，別忘了告訴我……”
“好啊，不過(guò)到時(shí)你可得請(qǐng)我吃飯啊！”小P道。
“那是當(dāng)然……”老C笑道，“我們關(guān)于遞推的討論先暫時(shí)告一段落，我覺(jué)得你差不多也算上道了，所以我們開始要進(jìn)行一些更有趣的活動(dòng)……”
“……”小P無(wú)語(yǔ)，“你又找到什么好館子了？”
“……”老C囧，“不是，是我覺(jué)得應(yīng)當(dāng)可以系統(tǒng)的開始一些工作了。”
“哦？什么是系統(tǒng)的工作？”小P不解。
“還記得《Teach Yourself Programming
in Ten Years》嗎？這本書提到，在項(xiàng)目中學(xué)習(xí)是很好很強(qiáng)大的。因此……我們現(xiàn)在可以開始一個(gè)項(xiàng)目了。”老C回答。
“哦？什么項(xiàng)目？”小P奇道。
“先從一個(gè)桌面計(jì)算器開始吧。”老C說(shuō)道，“一個(gè)自由風(fēng)格的計(jì)算器，可以對(duì)數(shù)學(xué)運(yùn)算進(jìn)行計(jì)算，并可以進(jìn)行一些簡(jiǎn)單的公式計(jì)算。”他想想，“就像最簡(jiǎn)單的matlab。”
“是嗎？”小P興奮道，“這真是很酷的事情。”
“既然要做，我們就很正規(guī)、正式、正經(jīng)、正確、正……哦，”看到小P幽怨的眼神，老C趕快打住，“我們就按照正規(guī)的、科學(xué)的過(guò)程來(lái)做。”
“那么怎么才算是正規(guī)和科學(xué)呢？”小P追問(wèn)。
“很好，”老C滿意的點(diǎn)頭，“希望你保持這種旺盛的求知欲望。”他找到杯子喝了一口水，“所謂正規(guī)和科學(xué)，是使得我們的開發(fā)活動(dòng)有序、可控和可度量。如何
做到這些，我也無(wú)法一時(shí)說(shuō)清楚，等到我們進(jìn)行一段時(shí)間，你可能就會(huì)產(chǎn)生一些體會(huì)了。你記住現(xiàn)在腦海中產(chǎn)生的問(wèn)題，讓我們?cè)趯?shí)踐中慢慢解答。但是在開始我們
的項(xiàng)目之前，還有一些鋪墊的東西必須先進(jìn)行一下。”
“哦？有哪些呢？”小P問(wèn)道。
“技術(shù)和技能可以一邊隨著項(xiàng)目的進(jìn)行一邊訓(xùn)練，但一些知識(shí)性的問(wèn)題要先來(lái)。”老C回答，“第一，我們要先學(xué)習(xí)一下遞歸下降語(yǔ)法分析；第二，我們還要學(xué)習(xí)一
下有限狀態(tài)機(jī)；第三，我們要了解一些配置管理方面的知識(shí)；第四，了解一些簡(jiǎn)單的關(guān)于項(xiàng)目方面的概念；當(dāng)這些問(wèn)題我們都有過(guò)一些簡(jiǎn)單的討論后，我們就可以開
始一個(gè)簡(jiǎn)單的關(guān)于桌面計(jì)算器的小項(xiàng)目啦，而在所有這些過(guò)程中，我們都會(huì)穿插進(jìn)行一些數(shù)據(jù)結(jié)構(gòu)與算法的討論。”
“是么？我倒是有些迫不及待啦。”小P應(yīng)道。看到老C指著肚子，小P笑道，“當(dāng)然，我會(huì)請(qǐng)你吃頓好的，因?yàn)楹ε履悴厮截洠晕覜Q定下血本請(qǐng)你吃麻辣燙……”
兩人一邊說(shuō)笑，一邊到隔壁叫上同學(xué)，殺出門外……