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