“看來(lái)我們就有了一個(gè)求通項(xiàng)是n的線性關(guān)系的數(shù)列的前n項(xiàng)和的工具了？”小P一邊吸著在回教研室的路上買的酸奶一邊問(wèn)。
“不僅僅是這樣，根據(jù)前人的經(jīng)驗(yàn)總結(jié)，求解遞歸問(wèn)題最后往往會(huì)歸結(jié)為一個(gè)求數(shù)列前n項(xiàng)和的問(wèn)題。”老C喝著他的茶水，“我們現(xiàn)在只是進(jìn)行一些知識(shí)儲(chǔ)備而
已。而且有了現(xiàn)在的這個(gè)工具，我們還可以求一些更復(fù)雜的數(shù)列求和問(wèn)題。”老C說(shuō)著將白板擦干凈，將已經(jīng)掌握的公式寫在最上面。
若
T0 = α
Tn = Tn-1 + β + γn
則
Tn = α + βn + γn(n + 1)/2
“現(xiàn)在要求一個(gè)稍微復(fù)雜一些的數(shù)列的前n項(xiàng)和，”老C說(shuō)著在白板上寫下問(wèn)題，“提醒你可以用我們剛才得到的公式求解……這樣解決問(wèn)題的方法就限定在很小的區(qū)域了，省得你東想西想……這樣求解問(wèn)題就變得稍微容易一些了……因?yàn)槲覀兊墓骄褪蔷€索……”
求
的通項(xiàng)公式。
“呵呵，好好想想吧，答案就在我們已有的公式上。”說(shuō)完老C跑到一旁一邊喝茶一邊竊笑。
“哦？”小P瞇起眼睛，“讓我想想，應(yīng)當(dāng)可以做出來(lái)的……”
“好的，你做出來(lái)了后就給我講講吧，我也一同學(xué)習(xí)學(xué)習(xí)。”老C說(shuō)完就跑到自己的電腦上噼里啪啦的忙起來(lái)。
一個(gè)小時(shí)后……
“唉，老C，你幫我看看，我為甚做出來(lái)的結(jié)果有些問(wèn)題，但是我又發(fā)現(xiàn)不了錯(cuò)誤在什么地方……”小P跑過(guò)去拍拍老C。
“哦？是么？”老C扭過(guò)椅子，“你是怎么做的呢？”
“嗯，你看看我是這樣推導(dǎo)的。”小P說(shuō)著將他的推導(dǎo)過(guò)程抄到白板上。
又T0 = 02 = 0
所以原問(wèn)題可以轉(zhuǎn)化為求
T0 = 0
的通項(xiàng)
“看，這樣就轉(zhuǎn)化為一個(gè)求遞推公式的通項(xiàng)問(wèn)題。”小P說(shuō)道，“但是我們手頭上求遞推公式通項(xiàng)的工具就只有一個(gè)，為了達(dá)到使用此工具求解問(wèn)題的目的，經(jīng)過(guò)我殫精竭慮的多方考慮，我決定……在等式兩邊求導(dǎo)……”
“咦？你的想法……很好很強(qiáng)大啊，真的是很具有想象力嘛……”老C贊嘆。
“是啊是啊，到目前為止還比較順利，但是問(wèn)題就是不知道出在什么地方……”小P道，然后接著向下寫。
令
所以原方程可以化簡(jiǎn)為
Sn = Sn-1 + 2n
又可得
S0 = 2 * 0 = 0
所以根據(jù)已知公式得到
Sn = n(n + 1)
又有
所以
Tn = n3/3 + n2/2
又因?yàn)?
T0 = 02 = 0
所以
C = 0
所以
Tn = n3/3 + n2/2
“看，這個(gè)就是我的解答，但是在代入n = 1, 2, 3…進(jìn)行檢查的時(shí)候發(fā)現(xiàn)并不正確……我看了好幾遍，都不知道問(wèn)題在什么地方……”小P委屈的說(shuō)道。
“唔……我來(lái)看看。”老C搬過(guò)椅子坐在白板前，仔細(xì)觀看起推導(dǎo)過(guò)程來(lái)……“這里為什么是S0 = 2 * 0 = 0？”老C問(wèn)道。
“是這樣，”小P解釋，“因?yàn)槲艺J(rèn)為可以將Sn = Sn-1 + 2n看為一個(gè)求和，令an = 2n，這樣原來(lái)的式子就可以看成對(duì)數(shù)列an求前n項(xiàng)和。而S0 = a0 = 2*n = 2*0 = 0……”
“……你啊在這里犯了一個(gè)經(jīng)典的錯(cuò)誤……”老C說(shuō)道，“為了紀(jì)念你犯的錯(cuò)誤，我決定將這個(gè)錯(cuò)誤命名為小P之由遞推公式得到邊界錯(cuò)誤。”看到小P還是不明
白，老C接著說(shuō)道，“現(xiàn)在的這個(gè)問(wèn)題對(duì)于我這種智商比較低的人，是一時(shí)無(wú)法和你說(shuō)清楚的，與我們一般討論問(wèn)題的思路相同，我們來(lái)看看一個(gè)更簡(jiǎn)單的例子。”
說(shuō)罷老C在白板上寫下一個(gè)求和問(wèn)題。
“我們知道Tn的通項(xiàng)可以寫為n(n+1)/2，把這個(gè)結(jié)論作為我們驗(yàn)證問(wèn)題的工具。現(xiàn)在看看使用你的方法會(huì)造成什么結(jié)果。”說(shuō)完老C繼續(xù)在白板上比劃。
令
令
an = 1
因?yàn)?
所以
S0 = 0
Sn = n
則
得
Tn = n2/2 + C
因?yàn)門0 = 0，所以C = 0
所以
Tn = n2/2
“看，推導(dǎo)結(jié)果和我們已經(jīng)知道的結(jié)果不一樣！”老C說(shuō)道，“讓我們看看哪一步出的問(wèn)題。”他在白板上畫了一個(gè)箭頭，指向一行推導(dǎo)。
“我們現(xiàn)在把Tn = n(n+1)/2代入這個(gè)公式，看看出了什么問(wèn)題。”老C說(shuō)道。
“看看，其實(shí)我們可以根據(jù)這個(gè)公式得到Sn = (2n+1)/2的，所以S0 = 1，”說(shuō)完他又強(qiáng)調(diào)，“為什么你會(huì)得到S0 = 0這樣錯(cuò)誤的結(jié)論呢？因?yàn)槟沐e(cuò)誤的認(rèn)為可以用a0 來(lái)求出S0！但是當(dāng)a0出現(xiàn)時(shí)，根據(jù)遞歸公式必然出現(xiàn)S-1，而S-1是
沒(méi)有定義的！記住永遠(yuǎn)無(wú)法從遞推項(xiàng)得到遞推邊界的值，就像無(wú)法從微分方程本身得到邊界值一樣！”老C說(shuō)道，“為了紀(jì)念你這個(gè)錯(cuò)誤并且讓你在數(shù)學(xué)的發(fā)展史上
留下深刻的印記，我把這個(gè)錯(cuò)誤稱為小P之從遞推公式得到邊界錯(cuò)誤！”看到小P有些囧，他笑道，“呵呵，開玩笑的。但是這樣一個(gè)錯(cuò)誤的確是很經(jīng)典的，所以你
一定要記住，永遠(yuǎn)無(wú)法從遞推本身看出遞推結(jié)束的條件，這個(gè)條件需要從外部給出！”
“哦？的確是這樣啊，因?yàn)槲矣肋h(yuǎn)沒(méi)有辦法從一個(gè)微分方程中看出微分方程的邊界值的……因?yàn)槲⒎址匠讨粫?huì)解出通解，特解需要特別的邊界條件。好像遞推方程也
一樣……就像我無(wú)法僅用當(dāng)前汽車的加速度就看出它在下一時(shí)刻的速度，因?yàn)槌跏紩r(shí)刻的速度信息必須由另外一個(gè)條件給出的……”小P回答，“現(xiàn)在我恍然大悟
啦，我不應(yīng)當(dāng)從遞推項(xiàng)中推出邊界，而應(yīng)當(dāng)根據(jù)原來(lái)的求和公式中求出邊界的值。現(xiàn)在我知道我的錯(cuò)誤在哪里了。”說(shuō)完他繼續(xù)在白板上寫下求平方和通式的新推導(dǎo)
過(guò)程。
令
S0 =α
Sn = Sn-1 + 2n
根據(jù)遞推到通項(xiàng)的結(jié)論，得
Sn = α + n2 + n
對(duì)方程兩邊積分，得
Tn = αn + n3/3 + n2/2+C
因?yàn)?
T0 = 0，得C = 0
Tn = n2，所以求得上面方程一個(gè)特解為T1 = 1，n = 1，代入通項(xiàng)公式得
1 = 5/6 + α
所以
α = 1/6
所以原通項(xiàng)可以寫為
Tn = n3/3 + n2/2 + 1/6n
“呵呵，這下就對(duì)了！”小P又代入幾個(gè)n值驗(yàn)算了一下。
“這下你是否有些明白？”老C問(wèn)道，“其實(shí)我們可以通過(guò)我們的結(jié)論得到很多的數(shù)列和的通項(xiàng)公式。”
“是啊，只要我們使用微積分，可以得到很多有趣的結(jié)論。”小P說(shuō)道。
“嗯，的確，但是只使用微積分是遠(yuǎn)遠(yuǎn)不夠的，”老C說(shuō)道，“因?yàn)橐婚_始的那個(gè)通項(xiàng)公式無(wú)法使用微積分的方法從我們得到的簡(jiǎn)單公式推導(dǎo)出來(lái)。現(xiàn)在我們來(lái)看
看，經(jīng)過(guò)我們一番探索后，有什么好的方法可以去求解那個(gè)問(wèn)題。”老C說(shuō)完將白板擦干凈，把需要求解的通項(xiàng)公式寫在了正中間。
T0 = T0
anTn = bnTn-1 + cn
“怎么樣，有什么想法沒(méi)有？”老C問(wèn)道。
“如果我可以有一個(gè)Rn = anTn，且Rn-1 = bnTn-1，那么我就可以將原來(lái)的遞推公式變?yōu)橐粋€(gè)對(duì)cn的求和公式……但是世界上哪有這么好的事情，恰好可以找到一個(gè)Rn啊……”小P說(shuō)道。
“嗯，你的想法很好啊，沒(méi)錯(cuò)，我們是不能次次都找到這樣的Rn，但是我們可以通過(guò)某些方法構(gòu)造出來(lái)一個(gè)。”老C說(shuō)道，“最簡(jiǎn)單的，如果我們?cè)诠絻蛇呁瑫r(shí)乘上一個(gè)數(shù)列，比如sn，這樣我們就可以得到新的遞推數(shù)列。”
snanTn = snbnTn-1 + sncn
“看看，我們不用指望rp，而是通過(guò)自己的雙手，我們可以使得snanTn = Rn，snbnTn-1 = Rn-1，加一加，乘一乘，都是常用的構(gòu)造方法，你要在走投無(wú)路的時(shí)候考慮使用它們。”老C撓撓頭，“在這里，我們?cè)诘仁絻蛇呁说臄?shù)列sn在圈內(nèi)有一個(gè)學(xué)名，叫做summation factor，還是算作小有名氣的……”
“哦，下來(lái)我就可以求解這個(gè)遞推公式了！”忍受不了了老C的羅嗦，小P插嘴，然后在白板上演算起來(lái)。
令
Rn = snanTn，Rn-1 = snbnTn-1
則原式可以改寫為
Rn = Rn-1 + sncn
則
Rn = R0 + s1c1 + s2c2 + s3c3 +…+sncn
所以
下面求sn
因?yàn)?
Rn-1 = snbnTn-1
所以
Rn = sn+1bn＋1Tn
所以
snanTn = sn+1bn＋1Tn
即
sn+1bn＋1 ＝ snan
所以
“唔，這樣就差不多啦。”小P說(shuō)道，“因?yàn)閍n和bn是已知的，只要我選擇的s0不為0，那么就可以求出sn啦，然后遞推公式就轉(zhuǎn)換為求數(shù)列sncn的前n項(xiàng)和。”
“是啊是啊，然后我們的問(wèn)題就變?yōu)榍髷?shù)列前n項(xiàng)和的問(wèn)題了。”老C說(shuō)，“為了解決遞推問(wèn)題，我們發(fā)現(xiàn)需要解決數(shù)列求和問(wèn)題。看看，事情發(fā)生了奇妙的轉(zhuǎn)換。
所以我們以后還會(huì)繼續(xù)討論一些求數(shù)列和的問(wèn)題，畢竟遞推的思想是計(jì)算機(jī)科學(xué)中一個(gè)及其重要的思想，值得我們?cè)谶@方面下下功夫。以后我們很多的做法都會(huì)依賴
于遞推的這個(gè)基本的思想啦。”他站起來(lái)伸個(gè)懶腰，“不過(guò)僅僅依靠summation factor是不夠的，還有一些問(wèn)題是summation
factor無(wú)法解決的，小朋友吃蘋果問(wèn)題就是一個(gè)例子。”說(shuō)完老C笑道，“未知的事物總是多于已知事物嘛。不過(guò)……如果你在參加面試或筆試的時(shí)候?qū)嶋H上
很有可能不會(huì)碰到數(shù)到7的小朋友被踢出的問(wèn)題，一般都是數(shù)到2的小朋友被踢出。為什么？……因?yàn)槊嬖嚮蚬P試的時(shí)候時(shí)間有限，無(wú)法允許你寫一個(gè)長(zhǎng)長(zhǎng)的運(yùn)用
linked
list解決問(wèn)題所花費(fèi)的時(shí)間，而數(shù)到2的小朋友被踢出，實(shí)際上可以用一個(gè)循環(huán)左移的算法來(lái)解決。這個(gè)就是在數(shù)學(xué)圈里比較有名的Josephus問(wèn)
題……”看到小P已經(jīng)有些反應(yīng)不過(guò)來(lái)了，老C停止了長(zhǎng)篇大論，“算了，今天就到這里吧。我們明天再運(yùn)用遞歸的思想解決這個(gè)小朋友吃蘋果的問(wèn)題，順便再討論
一些對(duì)算法的效率進(jìn)行評(píng)估的方法……這些都是基礎(chǔ)，如果不了解這些就去盲目的學(xué)習(xí)C++語(yǔ)言、面向?qū)ο缶幊毯皖悗?kù)什么的，對(duì)你有害無(wú)益……因?yàn)槟愕乃枷刖?
會(huì)局限在一個(gè)比較低的水平上。”
“是嗎是嗎？”小P不解，“會(huì)嗎？”
“的確是這樣。”老C回答，“我們學(xué)習(xí)的是編程，而不僅僅學(xué)習(xí)的是語(yǔ)言。我們希望通過(guò)對(duì)語(yǔ)言的學(xué)習(xí)提高的是編程的能力……這樣你在以后的工作中，無(wú)論使用
什么語(yǔ)言，都會(huì)飛快的上手，同時(shí)分析問(wèn)題和解決問(wèn)題的能力也會(huì)有顯得眾不同……要深入進(jìn)去，這就是為什么說(shuō)teach yourself
programming in ten
years的原因……這10年中，你學(xué)習(xí)的如果僅僅是語(yǔ)言的話，那么等10年后，你會(huì)發(fā)現(xiàn)，自己原來(lái)沒(méi)有10年的編程經(jīng)驗(yàn)，有的只是10個(gè)1年編程經(jīng)
驗(yàn)……”
“呵呵，你這么說(shuō)還比較有趣啊，10個(gè)1年編程經(jīng)驗(yàn)……哈哈”小P笑道。
“唉，現(xiàn)在這樣的人不在少數(shù)啊。”老C感慨，“所以你要深練內(nèi)功。根據(jù)我的觀點(diǎn)，我們可以把自身的知識(shí)技能分為三類，一類是基本知識(shí)，一類是專業(yè)知識(shí)，一
類是基本素質(zhì)。基本知識(shí)是我們思維的根本，如果沒(méi)有這些知識(shí)，我們就會(huì)缺乏某些常識(shí)，對(duì)于編程的人員來(lái)說(shuō)，這部分知識(shí)代表了內(nèi)功，包括數(shù)學(xué)知識(shí)、算法知識(shí)
和數(shù)據(jù)結(jié)構(gòu)方面的知識(shí)；專業(yè)知識(shí)代表我們的經(jīng)驗(yàn)，在軟件來(lái)說(shuō)，可能包括一些面向?qū)ο蟮木幊趟枷搿⒛承┙Y(jié)構(gòu)化編程的方法、以及其他配置管理和項(xiàng)目生命期方面
的知識(shí)，也包括你所要從事的行業(yè)的知識(shí)，比如你要從事于自控行業(yè)，那么信號(hào)與系統(tǒng)、信號(hào)處理、自控原理、線性控制理論、現(xiàn)代控制理論等也是必須的專業(yè)知
識(shí)；基本素質(zhì)是我們思考問(wèn)題的方式方法，以及我們接人待物、和他人相處、溝通方面的能力。這三個(gè)方面交織在一起，無(wú)法有效的單獨(dú)訓(xùn)練某一方面，需要在一定
的環(huán)境下進(jìn)行系統(tǒng)的鍛煉。”
“哦？有這么復(fù)雜嘛？”小P不解。
“是啊是啊，如果你想成為優(yōu)秀的工程師或者科技工作者，既要深練內(nèi)功，努力提高個(gè)人素質(zhì)和基礎(chǔ)知識(shí)，也要鍛煉外功，做一個(gè)合格的實(shí)踐者。”老C感嘆，“這
兩者缺一不可，既要在理論上深入研究，也要懂得如何將理論正確的、良好的、具有工業(yè)強(qiáng)度的應(yīng)用于實(shí)踐。”他開始自吹自擂，“幸好兄弟我在這方面還有幾下散
手，沒(méi)事我們可以討論討論，切磋切磋……”
“呵呵，好啊。”小P點(diǎn)頭，飛快，“不過(guò)現(xiàn)在也不早了，我們還是閃人吧。”
“Ok，ok。”老C點(diǎn)頭，“我們就回吧，對(duì)了，上次你給我說(shuō)的魔獸用人類tower rush很是厲害，怎么我就沒(méi)有感覺(jué)呢……”
“呵呵，等回去了我給你操練操練……”小P笑道……
(下來(lái)有josephus問(wèn)題的一些討論，以及算法效率方面的一些基本討論，再后面是有限狀態(tài)機(jī)的討論，再再后面是標(biāo)準(zhǔn)輸入輸出庫(kù)的討論，再再再后面是配置管理的討論，再再再再后面是遞歸下降語(yǔ)法分析討論……總之哥倆要說(shuō)的事情還沒(méi)完沒(méi)了呢)