第二桶 基于對(duì)象的編程 第四碗 哥倆首談遞推模型 小P開求通項(xiàng)公式

     “雖然自然辯證法這個(gè)理論是絕對(duì)正確的，但是我總感覺對(duì)解決實(shí)際問題的幫助不是很大。”小P對(duì)老C說道。兩個(gè)人下了自然辯證法的課，向東2樓走去。一邊走小P一邊評(píng)論。

     “呵呵，”老C笑道，“雖然我們平時(shí)分析問題都是在靜態(tài)情況下分析和解決，但是，無論如何辯證法告訴我們這樣有可能是不正確的。因?yàn)槿祟愂苤橇ο拗疲荒? 在靜止的，片面的角度去分析問題——如果一次考慮了太多的外界因素，使用運(yùn)動(dòng)的觀點(diǎn)去看問題，反而會(huì)導(dǎo)致問題過于復(fù)雜以至于無法分析和解決。但是我們?cè)诮? 決問題以后也不要忘記在實(shí)踐中去檢驗(yàn)我們的解決問題的方法，因?yàn)椤q證法告訴我們——我們的解法雖然在理論上成立，但前提——我們是在一個(gè)割裂的和靜態(tài) 的環(huán)境中去考慮問題的——好像有可能是不恰當(dāng)?shù)摹?#8221;

     “哦？”小P點(diǎn)頭，“就是說辯證法最重要的作用是……提醒我們請(qǐng)?jiān)趯?shí)踐中檢查我們的理論……呵呵。”他騷騷一笑，“感覺辯證法的作用更像是一個(gè)錯(cuò)誤分析理 論，用來告訴我們錯(cuò)誤是怎樣發(fā)生的以及為什么會(huì)發(fā)生這種錯(cuò)誤，但是好像并不能非常有效的指導(dǎo)我們避免錯(cuò)誤，因?yàn)橐勒者@種理論去解決問題，好像就會(huì)陷入太多 的細(xì)節(jié)，需要考慮的因素太多，反而無法開始工作了……”

     “呵呵，”老C笑道，“那么我們就先靜態(tài)的、割裂的解決一個(gè)問題先。”說著兩個(gè)人走進(jìn)了教研室，他從角落里拉過來白板。“漢諾塔的故事你聽說過吧？”老C問。

     “嗯，這個(gè)題目我以前也做過，怎么？”小P問。

     “那樣更好，我就不用多費(fèi)口舌了。”老C說道，“現(xiàn)在的問題是，請(qǐng)你求解一下解決這個(gè)問題，總共需要多少步。不要死記硬背以前記過的公式，我知道你以前做 過，我們需要從原理一步一步推導(dǎo)下去，這樣才更有意義一些。”他攔住急于在白板上寫寫畫畫的小P，說道，“我們需要講究一些方法，也是一般我們解決問題的 思路，現(xiàn)在我們就照這個(gè)思路來進(jìn)行。”

     “哦？按照什么樣的思路？”小P問。

     “我們可以這樣想象一下，我們所有已經(jīng)掌握的知識(shí)就像工具箱，一個(gè)一個(gè)排列在我們的右手；我們面對(duì)的問題也是一個(gè)一個(gè)的小箱子，排列在我們的左手。我們首 先要熟悉我們的工具箱，知道工具箱里面的工具是應(yīng)對(duì)什么問題的，應(yīng)當(dāng)如何被使用——比如我們需要了解一個(gè)活動(dòng)扳手是如何擰緊螺母的；然后我們左手的問題箱 子需要被分類，歸結(jié)到我們可以依靠工具箱解決的一類與依靠我們目前的工具箱無法解決的一類——比如我們看到螺絲，就會(huì)想到用螺絲刀，而看到螺母，就會(huì)想到 用扳手，如果我們可以正確的對(duì)問題分類，對(duì)于可以使用工具箱中的工具解決的問題，那么從右手邊的工具箱中拿出工具——解決問題就行了；然后我們需要在實(shí)踐 中再檢驗(yàn)一下我們解決問題的效果，根據(jù)反饋的信息再對(duì)問題進(jìn)行進(jìn)一步的細(xì)分種類，選擇更加合適的工具——如此循環(huán)，直到問題被解決的程度可以被接受為止。 ”老C開始長(zhǎng)篇大論，“所以解決問題的過程實(shí)際是逆向思維的過程，一般來說逆向思維都帶有嘗試的性質(zhì)，試的好不好，那要看你的個(gè)人經(jīng)驗(yàn)和悟性。”

     “那么對(duì)于無法使用工具箱解決的問題呢？”小P說道。

     “呵呵，那就需要一些創(chuàng)造性的勞動(dòng)了。”老C回答。“如果我們對(duì)已經(jīng)有的工具的原理足夠了解，我們就可以用這些工具來生產(chǎn)一些新的工具來解決新的問題。” 他吞了一口唾沫，“但是我們也需要對(duì)遇到的問題進(jìn)行足夠的了解——了解它的某些特質(zhì)，使得我們制造工具的活動(dòng)不會(huì)變得很盲目。”

     “是嗎？”小P問，“那么如何開始呢？”

     “首先我們先簡(jiǎn)化問題，比如這個(gè)漢諾塔問題，我們可以先在3、5個(gè)碟子的情況下玩一玩，尋找一些規(guī)律。然后再考慮考慮此類問題如何被解決，通法是什么。” 他撓撓頭，“呵呵，那么我們就開始吧。由于我智力有限，一時(shí)無法理解n個(gè)盤子的漢諾塔問題，我們就先從3個(gè)盤子開始好不？盤子3表示最大的，在最底下，盤 子1表示最小的，在最上面；同樣我們也需要對(duì)桿子編號(hào)，最左面的叫1號(hào)，最右面的叫3號(hào)，你自己想想2號(hào)桿在什么地方……”

     “……好啊好啊，那么我們就先來試試吧。”說著小P在白板上畫了起來。

 

     “呵呵，畫的不好，像樹枝穿便便……”小P謙虛道。

     “……”老C一時(shí)無語(yǔ)。過了一陣子，老C止住惡心，問道，“你看看這幾副圖，有沒有發(fā)現(xiàn)什么規(guī)律？”

     “哦？什么意思？會(huì)有什么規(guī)律呢？”小P問。

     “可能現(xiàn)在圖太多了，讓我們抽象一些，我來擦掉幾副圖。”老C說道，然后他在白板上將某些圖擦去。

     “唔……”小P盯著看了一會(huì)兒，說道，“好像是經(jīng)過某些步數(shù)，將1號(hào)與2號(hào)盤子放到中間的桿子上，再將3號(hào)盤子放在最右邊的3號(hào)桿子上，然后再經(jīng)過某些步 數(shù)，將1號(hào)和2號(hào)在放到3號(hào)桿子上。”他想了想，道，“如果這樣看的話，好像移動(dòng)3個(gè)盤子的問題變?yōu)椋簩蓚€(gè)盤子移到第2個(gè)桿子，將3號(hào)盤子移到第3個(gè)桿 子，再將這兩個(gè)盤子移到第3個(gè)桿子。”

     “是的，的確是這樣。”老C贊嘆，“如果我用T_n表示從一個(gè)桿子移動(dòng)n個(gè)盤子到另一個(gè)桿子——比如從1號(hào)移到3號(hào)桿，所需要的步數(shù)，那么我們會(huì)得到什么呢？”

     “唔……”小P想了想，“好像是這樣，先將上面的(n-1)個(gè)盤子移到……無論什么地——比如說2號(hào)桿吧……這將需要T_n-1步，將最底下的第n個(gè)盤子從1號(hào)桿移到3號(hào)，這需要1步，再將那(n-1)個(gè)盤子從幫忙的桿子上移到我們的3號(hào)桿，還是需要T_n-1步……這樣我們得到T_n = T_n-1 + 1 + T_n-1 = 2T_n-1 + 1。”

     “嗯，的確是這樣，但是還不算完。”老C說道，“你看，我們得到了一個(gè)遞推的公式，但是……沒有推導(dǎo)的終點(diǎn)……我們必須在某點(diǎn)結(jié)束推導(dǎo)。”他說，“因?yàn)閚 >= 0，所以我們需要在n = 0時(shí)結(jié)束推導(dǎo)，這樣相當(dāng)容易，因?yàn)門₀ = 0……因?yàn)槿绻?個(gè)盤子需要移動(dòng)，我們什么都不用做，步數(shù)自然就是0了。”他繼續(xù)說道，“這樣我們就有了一組遞推數(shù)列。”于是他在白板上寫下了如下的公式。

 

T₀ = 0

T_n = 2T_n-1 + 1

 

     “看看，這樣問題就變?yōu)閷⑦@個(gè)遞推公式轉(zhuǎn)變?yōu)橥?xiàng)公式了。”老C說道，“發(fā)揮你強(qiáng)悍的數(shù)學(xué)知識(shí)，解決這個(gè)問題吧！”然后他幸災(zāi)樂禍的躲到一邊喝茶。

     “切，這個(gè)算什么，小case啦！”小P嘴硬道，“這些東西我高中就會(huì)玩了。”于是他拿起一支筆，在白板上涂涂抹抹起來，“唔，這樣……然后這樣……不對(duì)不對(duì)……應(yīng)當(dāng)這樣……嗯……”

     沒有理會(huì)小P的自言自語(yǔ)，老C慢慢的喝著茶水，跑去起點(diǎn)上看起了水文。

     半個(gè)小時(shí)后……

     “嗷！”小P突然喊道。

     “干什么！你……”老C嚇得從椅子上跳了起來。

     “我知道怎么做了！”小P興奮的說道。

     “哦？”老C覺得這個(gè)小家伙還是比較強(qiáng)悍的，“你是怎么做的？這么快就做出來啦？”

     “嘿嘿，”小P得意的說，“只要在兩邊同時(shí)處以2ⁿ就可以將問題轉(zhuǎn)化為求一個(gè)隊(duì)列的前n項(xiàng)和的問題。”說罷他指著白板上的一些演算。

 

T_n / 2ⁿ = 2T_n-1 / 2ⁿ + 2^-n

T_n / 2ⁿ = T_n-1 / 2^n－1 + 2^-n

令S_n = T_n / 2ⁿ，則S₀ = T₀ / 2⁰ = 0

那么原式可以轉(zhuǎn)化為：

S₀ = 0

S_n = S_n-1 + 2^-n

這個(gè)是等比數(shù)列a_n = 2^-n 數(shù)列前n項(xiàng)求和(n >= 1)。所以利用等比數(shù)列求和公式，

又S_n = T_n / 2ⁿ，所以

T_n = 2ⁿ * S_n = 2ⁿ(1 – 2^-n) = 2ⁿ – 1

所以

T_n = 2ⁿ – 1

 

     “看就是這樣求出來的。”小P得意的說道。

     “呵呵，你是怎么想到要用等比數(shù)列求和的呢？”老C問。

     “因?yàn)?#8230;…我只知道等差數(shù)列和等比數(shù)列的求和公式，我總要把問題轉(zhuǎn)化到我可以求解的范圍內(nèi)部啊，這樣才可以求解。”小P說道。

     “呵呵，你的想法很好啊，知道用已經(jīng)掌握的工具去制造新的工具來解決問題，不錯(cuò)不錯(cuò)……但是美中不足的是在這一過程中充滿了技巧和構(gòu)造，對(duì)于編程人員來 說，他們是比較不喜歡技巧和構(gòu)造的巧合的東西，因?yàn)檫@些比較難以編程實(shí)現(xiàn)。”老C打擊了一下小P，“不過你還是很厲害啊，這樣都可以想出來。”老C又補(bǔ)了 一顆糖。

     “……”小P一時(shí)不知道該說些什么。

     “好吧，現(xiàn)在我們使用超級(jí)無敵蠻力計(jì)算機(jī)來解決這個(gè)問題吧。”老C說道，“我們先使用計(jì)算機(jī)的無敵蠻力解算這個(gè)問題，然后我們來推導(dǎo)一些關(guān)于遞歸的常用公式，并總結(jié)一些常用的計(jì)算方法。”

     “唔，好吧。”小P說道，“編寫遞歸函數(shù)，這個(gè)我以前也學(xué)習(xí)過，一般就是分為兩個(gè)部分。一個(gè)是遞歸結(jié)束條件，放在函數(shù)內(nèi)部的前面，另外一部分是遞歸本身啦。”說著他打開電腦，新建立了一個(gè)工程，編寫了一個(gè)極其簡(jiǎn)單的函數(shù)。

 

main.cpp

 

#include <iostream>

 

int Times (int n);

 

int main()

{

    std::cout << "Please enter a number > 0: ";

    int n;

    std::cin >> n;

 

    int res = Times(n);

 

    std::cout << "The result is: " << res << std::endl;

   

    return 0;

}

 

int Times(int n)

{

    if (0 == n)

    {

        return 0;

    }

 

    return 2 * Times(n - 1) + 1;

}

 

     寫完后小P試著輸入幾個(gè)數(shù)字，并確認(rèn)了他設(shè)計(jì)的函數(shù)是正確的。

     “這樣做有一種暴力美學(xué)……”老C評(píng)論，“但是為了更加深入的了解到遞歸本身，我們還需要再繼續(xù)深入的討論一些其他的相關(guān)問題。”說罷他在白板上寫下一組公式。

 

a_nT_n = b_nT_n-1 + C_n

 

     “看，這個(gè)就是我們會(huì)遇到的某些遞歸問題的一種更一般的形式，其中a_n，b_n和c_n都是值隨著n變化的系數(shù)，而T_n是我們希望求解的數(shù)列通項(xiàng)。”老C說道，“如果讓我們一開始就求解這個(gè)東東，那么也太難了，我們先來解決一個(gè)更簡(jiǎn)化一些的問題——這也是我們解決問題時(shí)通常的思路——來找找靈感，看會(huì)帶來一些思索的線索。”

 

T₀ = α

T_n = T_n-1 + β + γn

 

     “看，我們簡(jiǎn)化了這個(gè)問題，使得遞推的增長(zhǎng)項(xiàng)成為一個(gè)n的線性項(xiàng)，這樣就可以大大簡(jiǎn)化剛才的問題。”老C道，“不要厭惡希臘字母，我相信你在數(shù)學(xué)書上看到 的希臘字母的次數(shù)絕對(duì)不會(huì)超過史詩(shī)級(jí)懸疑恐怖戰(zhàn)爭(zhēng)愛情巨作《伯羅奔尼撒戰(zhàn)記》的原本……但是，雖然問題被簡(jiǎn)化了，但是像我這種智力水平底下的人，還是無法 理解的，所以我要試著代入幾個(gè)n的值，看看究竟會(huì)有什么樣子的規(guī)律。”說著他在白板上擦出一大片的空白，開始在上面寫東西。

 

T₀ = α

T₁ = T₀ + β + γ

T₂ = T₁ + β + 2γ = (T₀ + β + γ) +β + 2γ = α+ 2β + 3γ

T₃ = T₂ + β + 3γ = (T₀ + 2β + 3γ) +β + 3γ = α + 3β + 6γ

 

“看……”老C說道，“我們似乎可以發(fā)現(xiàn)，其實(shí)T_n可以被分解為3個(gè)數(shù)列的和。”說完，他在白板的醒目位置寫下如下的式子。

 

T₀ = α

T_n = αA_n + βB_n + γC_n

 

     “就是說我們認(rèn)為，如果隊(duì)列T_n可以表示為T₀ =α; T_n =αA_n + βB_n + γC_n 的形式，那么對(duì)于任意的α、β和γ，只要α、β、γ這3個(gè)參數(shù)的值被確定，那么T_n一定也可以被表示為T₀ = α; T_n = T_n-1 + β + γn 的形式。”

     “……的確是這樣啊，你這樣將問題反過來描述一下，有什么意義呢？”小P不解。

     “呵呵，也就是說如果A_n、B_n、C_n的通項(xiàng)被確定和α、β、γ的值被確定，那么T_n就被確定；其中A_n、B_n、C_n是不變的數(shù)列，而α、β、γ是可以任意變化的參數(shù)，對(duì)應(yīng)不同的α、β、γ，T_n會(huì)具有不同的形式。”

     “……這些我都已經(jīng)了解了……”小P嘟嘟囔囔。

     “看看……”老C沒有理會(huì)小P的嘟囔，“這就是一個(gè)典型的待定系數(shù)問題，如果我們將A_n、B_n、C_n看作系數(shù)，而將α、β、γ看作變量，通過給出不同的α、β、γ值和對(duì)應(yīng)的T_n值，就可以求出相應(yīng)的A_n、B_n、C_n。”

     “哦？”小P停止了心不在焉，“那么怎么才可以根據(jù)α、β、γ的值找到對(duì)應(yīng)的T_n值，然后反過來求出A_n、B_n、C_n呢？”

     “可以先找到一個(gè)特定的T_n通項(xiàng)，再根據(jù)T₀ = α 和T_n = T_n-1 + β + γn 來猜測(cè)此T_n對(duì)應(yīng)的α、β、γ。好處是我們把根據(jù)α、β、γ和T_n = T_n-1 + β + γn 來猜測(cè)T_n的過程反了過來，因?yàn)閺?#945;、β、γ和T_n = T_n-1 + β + γn 來猜測(cè)T_n的過程是逆向思維，然而從T_n通項(xiàng)和T₀ = α、T_n = T_n-1 + β + γn來猜測(cè)T_n對(duì)應(yīng)的α、β、γ是正向思維——一般來說正向思維會(huì)比對(duì)應(yīng)的逆向思維來得簡(jiǎn)單許多啊。接下來的工作就是根據(jù)我們猜測(cè)的結(jié)果對(duì)A_n、B_n、C_n求解。”

     “那么應(yīng)當(dāng)怎么解呢？”小P問道。

     “其實(shí)就是和一般的待定系數(shù)法的思想是一樣的，給出一個(gè)我們已經(jīng)知道的特解——這個(gè)解一般都是比較容易看出來或者推導(dǎo)出來的——將這個(gè)特解代入原方程，并 化簡(jiǎn)，可以得到一個(gè)關(guān)于系數(shù)的方程；再猜測(cè)一個(gè)特解，代入原方程，化簡(jiǎn)后又得到一個(gè)關(guān)于系數(shù)的方程……如果我們得到待定系數(shù)個(gè)數(shù)的方程——比如我們待定3 個(gè)系數(shù)——我們可以通過3個(gè)特解得到3個(gè)關(guān)于這3個(gè)系數(shù)的方程，若這3個(gè)方程聯(lián)立后可解，那么我們就可以通過方程組解得這3個(gè)系數(shù)。”老C擦擦唾沫。

     “就像通常使用待定系數(shù)法一樣，我們可以試著從最簡(jiǎn)單的情況開始。”老C說，“我可以先假設(shè)T_n是一個(gè)常數(shù)數(shù)列，它的通項(xiàng)就是T_n = c，那么根據(jù)T₀ = α，我們可以得到α = c；根據(jù)T_n = T_n-1 + β + γn，可以得到c = c + β + γn，根據(jù)這個(gè)式子，我們可以得到一個(gè)解——解可能有很多個(gè)，但是我們只要得到一組解就可以了——β = 0，γ ＝ 0；這樣我們根據(jù)T_n的通項(xiàng)公式T_n =αA_n + βB_n + γC_n就知道了在α = c，β = 0，γ ＝ 0的情況下，T_n是一個(gè)常數(shù)數(shù)列T_n = c，而在α = c，β = 0，γ ＝ 0的情況下T_n = αA_n + βB_n + γC_n可以化簡(jiǎn)為T_n = cA_n，而T_n實(shí)際上是T_n = c，所以c = cA_n，所以A_n = 1。”

     “哦？如果你把過程寫在白板上，我可能會(huì)更清楚一些。”小P說道。

     “好的。”老C一邊答應(yīng)小P，一邊將推導(dǎo)的過程記錄在白板上，“在這里我們先找到一個(gè)特解，由于這個(gè)特解是如此的特殊，當(dāng)我們將這個(gè)解代入原方程——就是T_n =αA_n + βB_n + γC_n后，不用再通過聯(lián)立后面2個(gè)方程解方程組，系數(shù)A_n就很容易的被求出來了……買糕的佛祖，這個(gè)特解找的也太nb了。”

     “……是啊是啊……”小P奇怪自己怎么就找不到這樣一個(gè)奇妙的特解，“你還可以再找到2個(gè)特解嗎？因?yàn)槲覀冞€有2個(gè)待定的系數(shù)需要求解。”他問道。

     “嘻嘻，其實(shí)就是運(yùn)氣好，恰好猜出來而已。”老C謙虛的說，“不過猜也要有道理的猜，我們解決實(shí)際問題其實(shí)就是在有道理的猜嘛……”說著他又在白板上演算起來。“我們的第2個(gè)特解，是T_n = n，因?yàn)門_n = n可以表示成為n = (n-1) + 1，即T_n = T_n-1 + 1，所以我們的第2個(gè)特解很輕松的就出來了，根據(jù)T_n = T_n-1 + β + γn，我們可以猜測(cè)在T_n = n時(shí)，β = 1，γ = 0。而由T_n = n和T₀ = α，我們猜測(cè)α = 0也就很是合情合理了。所以我們又神奇的得到第2個(gè)特解：T_n = n，α = 0，β = 1，γ = 0。現(xiàn)在我們要做的就是將這個(gè)特解代入原方程T_n = αA_n + βB_n + γC_n，來得到我們的第2個(gè)關(guān)于A_n、B_n、C_n的方程。”

      “呵呵，這個(gè)步驟就由我來完成吧。”小P忍不住也想比劃比劃，“這樣將T_n = n，α = 0，β = 1，γ = 0代入原方程，我們得到n = B_n，不會(huì)吧，B_n也這么容易的就求出來了？”小P有些佩服老C的rp了。

      “嗯，看來我們的rp保持了較高的水準(zhǔn)。”老C贊嘆道，“下一組我決定使用T_n = n²，因?yàn)閚² = (n - 1)² – 1 + 2n，所以T_n可以表示為T_n = T_n-1 -1 +2n，根據(jù)T_n = T_n-1 + β + γn，我們又可以很輕易的猜測(cè)出β = -1，γ ＝ 2，根據(jù)T₀ = α可以得到α = T₀ = 0² = 0，這樣第3個(gè)特解就是T_n = n²，α = 0，β = -1，γ ＝ 2……”

     “我來我來……”小P道，他一邊說，一邊在白板上演算，“將T_n = n²，α = 0，β = -1，γ ＝ 2代入原方程T_n = αA_n + βB_n + γC_n，得到n² = -B_n + 2C_n，看來在這里我們還需要和先前的2個(gè)系數(shù)方程進(jìn)行聯(lián)立了，不過也很簡(jiǎn)單，因?yàn)橐呀?jīng)求出B_n = n了，代入n² = -B_n + 2C_n，得到n² = -n + 2C_n，所以C_n = n(n + 1)/2。”

     “現(xiàn)在我們可以總結(jié)一下啦，如果一個(gè)數(shù)列具有T₀ = α，T_n = T_n-1 + β + γn的遞推公式，那么它的通項(xiàng)總可以寫為T₀ = α，T_n = α + βn + γn(n + 1)/2。”老C說道，并將這個(gè)結(jié)論寫在了白板上。

     “那么這個(gè)結(jié)論有什么用處呢？”小P問道。

     “問得好。”老C回答，“這樣我們起碼可以確定形狀和下面這個(gè)求和公式類似的問題的解啦。”說罷他在白板上寫下一個(gè)公式。

     “因?yàn)轭愃频那蠛凸娇梢员硎緸橐粋€(gè)遞推公式，且形式與我們剛才求解的遞推公式類似，所以我們可以很輕松的運(yùn)用我們剛才的結(jié)論求解此類求和問題。”說罷老C又在白板上繼續(xù)比劃起來。

     “看看，除了我們觀察問題的地方從希臘遨游回到一個(gè)和陜西差不多大的小島，其余沒有什么質(zhì)的變化。”老C道，“我們先去吃飯，等回來我們?cè)僮鲆恍┚毩?xí)來熟悉這個(gè)工具，為以后的應(yīng)用做些準(zhǔn)備。”

(這不是他們今天談?wù)摰乃袃?nèi)容)

posted on 2009-03-16 22:06 Anderson 閱讀(1734) 評(píng)論(2)  編輯 收藏 引用