第二桶 基于對象的編程 第五碗 哥倆再談遞推模型 小P二解通項公式

     “看來我們就有了一個求通項是n的線性關系的數列的前n項和的工具了？”小P一邊吸著在回教研室的路上買的酸奶一邊問。

     “不僅僅是這樣，根據前人的經驗總結，求解遞歸問題最后往往會歸結為一個求數列前n項和的問題。”老C喝著他的茶水，“我們現在只是進行一些知識儲備而 已。而且有了現在的這個工具，我們還可以求一些更復雜的數列求和問題。”老C說著將白板擦干凈，將已經掌握的公式寫在最上面。

 

若

T₀ = α

T_n = T_n-1 + β + γn

則

T_n = α + βn + γn(n + 1)/2

 

      “現在要求一個稍微復雜一些的數列的前n項和，”老C說著在白板上寫下問題，“提醒你可以用我們剛才得到的公式求解……這樣解決問題的方法就限定在很小的區域了，省得你東想西想……這樣求解問題就變得稍微容易一些了……因為我們的公式就是線索……”

 

求

的通項公式。

 

      “呵呵，好好想想吧，答案就在我們已有的公式上。”說完老C跑到一旁一邊喝茶一邊竊笑。

      “哦？”小P瞇起眼睛，“讓我想想，應當可以做出來的……”

      “好的，你做出來了后就給我講講吧，我也一同學習學習。”老C說完就跑到自己的電腦上噼里啪啦的忙起來。

      一個小時后……

      “唉，老C，你幫我看看，我為甚做出來的結果有些問題，但是我又發現不了錯誤在什么地方……”小P跑過去拍拍老C。

      “哦？是么？”老C扭過椅子，“你是怎么做的呢？”

      “嗯，你看看我是這樣推導的。”小P說著將他的推導過程抄到白板上。

 

又T₀ = 0² = 0

所以原問題可以轉化為求

T₀ = 0

      “看，這樣就轉化為一個求遞推公式的通項問題。”小P說道，“但是我們手頭上求遞推公式通項的工具就只有一個，為了達到使用此工具求解問題的目的，經過我殫精竭慮的多方考慮，我決定……在等式兩邊求導……”

      “咦？你的想法……很好很強大啊，真的是很具有想象力嘛……”老C贊嘆。

      “是啊是啊，到目前為止還比較順利，但是問題就是不知道出在什么地方……”小P道，然后接著向下寫。

 

令

所以原方程可以化簡為

S_n = S_n-1 + 2n

又可得

S₀ = 2 * 0 = 0

所以根據已知公式得到

S_n = n(n + 1)

又有

所以

T_n = n³/3 + n²/2

又因為

T₀ = 0² = 0

所以

C = 0

所以

T_n = n³/3 + n²/2

 

      “看，這個就是我的解答，但是在代入n = 1, 2, 3…進行檢查的時候發現并不正確……我看了好幾遍，都不知道問題在什么地方……”小P委屈的說道。

      “唔……我來看看。”老C搬過椅子坐在白板前，仔細觀看起推導過程來……“這里為什么是S₀ = 2 * 0 = 0？”老C問道。

      “是這樣，”小P解釋，“因為我認為可以將S_n = S_n-1 + 2n看為一個求和，令a_n = 2n，這樣原來的式子就可以看成對數列a_n求前n項和。而S₀ = a₀ = 2*n = 2*0 = 0……”

      “……你啊在這里犯了一個經典的錯誤……”老C說道，“為了紀念你犯的錯誤，我決定將這個錯誤命名為小P之由遞推公式得到邊界錯誤。”看到小P還是不明 白，老C接著說道，“現在的這個問題對于我這種智商比較低的人，是一時無法和你說清楚的，與我們一般討論問題的思路相同，我們來看看一個更簡單的例子。” 說罷老C在白板上寫下一個求和問題。

 

      “我們知道T_n的通項可以寫為n(n+1)/2，把這個結論作為我們驗證問題的工具。現在看看使用你的方法會造成什么結果。”說完老C繼續在白板上比劃。

 

令

令

a_n = 1

因為

所以

S₀ = 0

S_n = n

則

得

T_n = n²/2 + C

因為T₀ = 0，所以C = 0

所以

T_n = n²/2

 

      “看，推導結果和我們已經知道的結果不一樣！”老C說道，“讓我們看看哪一步出的問題。”他在白板上畫了一個箭頭，指向一行推導。

 

 

      “我們現在把T_n = n(n+1)/2代入這個公式，看看出了什么問題。”老C說道。

 

      “看看，其實我們可以根據這個公式得到S_n = (2n+1)/2的，所以S₀ = 1，”說完他又強調，“為什么你會得到S₀ = 0這樣錯誤的結論呢？因為你錯誤的認為可以用a₀ 來求出S₀！但是當a₀出現時，根據遞歸公式必然出現S_-1，而S_-1是 沒有定義的！記住永遠無法從遞推項得到遞推邊界的值，就像無法從微分方程本身得到邊界值一樣！”老C說道，“為了紀念你這個錯誤并且讓你在數學的發展史上 留下深刻的印記，我把這個錯誤稱為小P之從遞推公式得到邊界錯誤！”看到小P有些囧，他笑道，“呵呵，開玩笑的。但是這樣一個錯誤的確是很經典的，所以你 一定要記住，永遠無法從遞推本身看出遞推結束的條件，這個條件需要從外部給出！”

      “哦？的確是這樣啊，因為我永遠沒有辦法從一個微分方程中看出微分方程的邊界值的……因為微分方程只會解出通解，特解需要特別的邊界條件。好像遞推方程也 一樣……就像我無法僅用當前汽車的加速度就看出它在下一時刻的速度，因為初始時刻的速度信息必須由另外一個條件給出的……”小P回答，“現在我恍然大悟 啦，我不應當從遞推項中推出邊界，而應當根據原來的求和公式中求出邊界的值。現在我知道我的錯誤在哪里了。”說完他繼續在白板上寫下求平方和通式的新推導 過程。

 

令

S₀ =α

S_n = S_n-1 + 2n

根據遞推到通項的結論，得

S_n = α + n² + n

對方程兩邊積分，得

T_n = αn + n³/3 + n²/2+C

因為

T₀ = 0，得C = 0

T_n = n²，所以求得上面方程一個特解為T₁ = 1，n = 1，代入通項公式得

1 = 5/6 + α

所以

α = 1/6

所以原通項可以寫為

T_n = n³/3 + n²/2 + 1/6n

 

      “呵呵，這下就對了！”小P又代入幾個n值驗算了一下。

      “這下你是否有些明白？”老C問道，“其實我們可以通過我們的結論得到很多的數列和的通項公式。”

      “是啊，只要我們使用微積分，可以得到很多有趣的結論。”小P說道。

      “嗯，的確，但是只使用微積分是遠遠不夠的，”老C說道，“因為一開始的那個通項公式無法使用微積分的方法從我們得到的簡單公式推導出來。現在我們來看 看，經過我們一番探索后，有什么好的方法可以去求解那個問題。”老C說完將白板擦干凈，把需要求解的通項公式寫在了正中間。

 

T₀ = T₀

 

      “怎么樣，有什么想法沒有？”老C問道。

      “如果我可以有一個R_n = a_nT_n，且R_n-1 = b_nT_n-1，那么我就可以將原來的遞推公式變為一個對c_n的求和公式……但是世界上哪有這么好的事情，恰好可以找到一個R_n啊……”小P說道。

      “嗯，你的想法很好啊，沒錯，我們是不能次次都找到這樣的R_n，但是我們可以通過某些方法構造出來一個。”老C說道，“最簡單的，如果我們在公式兩邊同時乘上一個數列，比如s_n，這樣我們就可以得到新的遞推數列。”

 

 

      “看看，我們不用指望rp，而是通過自己的雙手，我們可以使得s_na_nT_n = R_n，s_nb_nT_n-1 = R_n-1，加一加，乘一乘，都是常用的構造方法，你要在走投無路的時候考慮使用它們。”老C撓撓頭，“在這里，我們在等式兩邊同乘的數列s_n在圈內有一個學名，叫做summation factor，還是算作小有名氣的……”

      “哦，下來我就可以求解這個遞推公式了！”忍受不了了老C的羅嗦，小P插嘴，然后在白板上演算起來。

 

令

R_n = s_na_nT_n，R_n-1 = s_nb_nT_n-1

則原式可以改寫為

R_n = R_n-1 + s_nc_n

則

R_n = R₀ + s₁c₁ + s₂c₂ + s₃c₃ +…+s_nc_n

所以

下面求s_n

因為

R_n-1 = s_nb_nT_n-1

所以

R_n = s_n+1b_n＋1T_n

所以

s_na_nT_n = s_n+1b_n＋1T_n

即

s_n+1b_n＋1 ＝ s_na_n

所以

 

      “唔，這樣就差不多啦。”小P說道，“因為a_n和b_n是已知的，只要我選擇的s₀不為0，那么就可以求出s_n啦，然后遞推公式就轉換為求數列s_nc_n的前n項和。”

      “是啊是啊，然后我們的問題就變為求數列前n項和的問題了。”老C說，“為了解決遞推問題，我們發現需要解決數列求和問題。看看，事情發生了奇妙的轉換。 所以我們以后還會繼續討論一些求數列和的問題，畢竟遞推的思想是計算機科學中一個及其重要的思想，值得我們在這方面下下功夫。以后我們很多的做法都會依賴 于遞推的這個基本的思想啦。”他站起來伸個懶腰，“不過僅僅依靠summation factor是不夠的，還有一些問題是summation factor無法解決的，小朋友吃蘋果問題就是一個例子。”說完老C笑道，“未知的事物總是多于已知事物嘛。不過……如果你在參加面試或筆試的時候實際上 很有可能不會碰到數到7的小朋友被踢出的問題，一般都是數到2的小朋友被踢出。為什么？……因為面試或筆試的時候時間有限，無法允許你寫一個長長的運用 linked list解決問題所花費的時間，而數到2的小朋友被踢出，實際上可以用一個循環左移的算法來解決。這個就是在數學圈里比較有名的Josephus問 題……”看到小P已經有些反應不過來了，老C停止了長篇大論，“算了，今天就到這里吧。我們明天再運用遞歸的思想解決這個小朋友吃蘋果的問題，順便再討論 一些對算法的效率進行評估的方法……這些都是基礎，如果不了解這些就去盲目的學習C++語言、面向對象編程和類庫什么的，對你有害無益……因為你的思想就 會局限在一個比較低的水平上。”

      “是嗎是嗎？”小P不解，“會嗎？”

      “的確是這樣。”老C回答，“我們學習的是編程，而不僅僅學習的是語言。我們希望通過對語言的學習提高的是編程的能力……這樣你在以后的工作中，無論使用 什么語言，都會飛快的上手，同時分析問題和解決問題的能力也會有顯得眾不同……要深入進去，這就是為什么說teach yourself programming in ten years的原因……這10年中，你學習的如果僅僅是語言的話，那么等10年后，你會發現，自己原來沒有10年的編程經驗，有的只是10個1年編程經 驗……”

      “呵呵，你這么說還比較有趣啊，10個1年編程經驗……哈哈”小P笑道。

      “唉，現在這樣的人不在少數啊。”老C感慨，“所以你要深練內功。根據我的觀點，我們可以把自身的知識技能分為三類，一類是基本知識，一類是專業知識，一 類是基本素質。基本知識是我們思維的根本，如果沒有這些知識，我們就會缺乏某些常識，對于編程的人員來說，這部分知識代表了內功，包括數學知識、算法知識 和數據結構方面的知識；專業知識代表我們的經驗，在軟件來說，可能包括一些面向對象的編程思想、某些結構化編程的方法、以及其他配置管理和項目生命期方面 的知識，也包括你所要從事的行業的知識，比如你要從事于自控行業，那么信號與系統、信號處理、自控原理、線性控制理論、現代控制理論等也是必須的專業知 識；基本素質是我們思考問題的方式方法，以及我們接人待物、和他人相處、溝通方面的能力。這三個方面交織在一起，無法有效的單獨訓練某一方面，需要在一定 的環境下進行系統的鍛煉。”

      “哦？有這么復雜嘛？”小P不解。

      “是啊是啊，如果你想成為優秀的工程師或者科技工作者，既要深練內功，努力提高個人素質和基礎知識，也要鍛煉外功，做一個合格的實踐者。”老C感嘆，“這 兩者缺一不可，既要在理論上深入研究，也要懂得如何將理論正確的、良好的、具有工業強度的應用于實踐。”他開始自吹自擂，“幸好兄弟我在這方面還有幾下散 手，沒事我們可以討論討論，切磋切磋……”

      “呵呵，好啊。”小P點頭，飛快，“不過現在也不早了，我們還是閃人吧。”

      “Ok，ok。”老C點頭，“我們就回吧，對了，上次你給我說的魔獸用人類tower rush很是厲害，怎么我就沒有感覺呢……”

      “呵呵，等回去了我給你操練操練……”小P笑道……

 

(下來有josephus問題的一些討論，以及算法效率方面的一些基本討論，再后面是有限狀態機的討論，再再后面是標準輸入輸出庫的討論，再再再后面是配置管理的討論，再再再再后面是遞歸下降語法分析討論……總之哥倆要說的事情還沒完沒了呢)

posted on 2009-03-22 19:37 Anderson 閱讀(1546) 評論(3)  編輯 收藏 引用