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

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

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

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

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

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

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

     “哦？按照什么樣的思路？”小P問(wèn)。

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

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

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

     “是嗎？”小P問(wèn)，“那么如何開(kāi)始呢？”

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

     “……好啊好啊，那么我們就先來(lái)試試吧。”說(shuō)著小P在白板上畫(huà)了起來(lái)。

 

     “呵呵，畫(huà)的不好，像樹(shù)枝穿便便……”小P謙虛道。

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

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

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

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

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

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

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

 

T₀ = 0

T_n = 2T_n-1 + 1

 

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

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

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

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

     “嗷！”小P突然喊道。

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

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

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

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

 

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

 

     “看就是這樣求出來(lái)的。”小P得意的說(shuō)道。

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

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

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

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

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

     “唔，好吧。”小P說(shuō)道，“編寫(xiě)遞歸函數(shù)，這個(gè)我以前也學(xué)習(xí)過(guò)，一般就是分為兩個(gè)部分。一個(gè)是遞歸結(jié)束條件，放在函數(shù)內(nèi)部的前面，另外一部分是遞歸本身啦。”說(shuō)著他打開(kāi)電腦，新建立了一個(gè)工程，編寫(xiě)了一個(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;

}

 

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

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

 

a_nT_n = b_nT_n-1 + C_n

 

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

 

T₀ = α

T_n = T_n-1 + β + γn

 

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

 

T₀ = α

T₁ = T₀ + β + γ

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

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

 

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

 

T₀ = α

T_n = αA_n + βB_n + γC_n

 

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

     “……的確是這樣啊，你這樣將問(wèn)題反過(guò)來(lái)描述一下，有什么意義呢？”小P不解。

     “呵呵，也就是說(shuō)如果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沒(méi)有理會(huì)小P的嘟囔，“這就是一個(gè)典型的待定系數(shù)問(wèn)題，如果我們將A_n、B_n、C_n看作系數(shù)，而將α、β、γ看作變量，通過(guò)給出不同的α、β、γ值和對(duì)應(yīng)的T_n值，就可以求出相應(yīng)的A_n、B_n、C_n。”

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

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

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

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

     “就像通常使用待定系數(shù)法一樣，我們可以試著從最簡(jiǎn)單的情況開(kāi)始。”老C說(shuō)，“我可以先假設(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(mén)_n = cA_n，而T_n實(shí)際上是T_n = c，所以c = cA_n，所以A_n = 1。”

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

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

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

     “嘻嘻，其實(shí)就是運(yùn)氣好，恰好猜出來(lái)而已。”老C謙虛的說(shuō)，“不過(guò)猜也要有道理的猜，我們解決實(shí)際問(wèn)題其實(shí)就是在有道理的猜嘛……”說(shuō)著他又在白板上演算起來(lái)。“我們的第2個(gè)特解，是T_n = n，因?yàn)門(mén)_n = n可以表示成為n = (n-1) + 1，即T_n = T_n-1 + 1，所以我們的第2個(gè)特解很輕松的就出來(lái)了，根據(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?，F(xiàn)在我們要做的就是將這個(gè)特解代入原方程T_n = αA_n + βB_n + γC_n，來(lái)得到我們的第2個(gè)關(guān)于A_n、B_n、C_n的方程。”

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

      “嗯，看來(lái)我們的rp保持了較高的水準(zhǔn)。”老C贊嘆道，“下一組我決定使用T_n = n²，因?yàn)閚² = (n - 1)² – 1 + 2n，所以T_n可以表示為T(mén)_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……”

     “我來(lái)我來(lái)……”小P道，他一邊說(shuō)，一邊在白板上演算，“將T_n = n²，α = 0，β = -1，γ ＝ 2代入原方程T_n = αA_n + βB_n + γC_n，得到n² = -B_n + 2C_n，看來(lái)在這里我們還需要和先前的2個(gè)系數(shù)方程進(jìn)行聯(lián)立了，不過(guò)也很簡(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)總可以寫(xiě)為T(mén)₀ = α，T_n = α + βn + γn(n + 1)/2。”老C說(shuō)道，并將這個(gè)結(jié)論寫(xiě)在了白板上。

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

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

     “因?yàn)轭?lèi)似的求和公式可以表示為一個(gè)遞推公式，且形式與我們剛才求解的遞推公式類(lèi)似，所以我們可以很輕松的運(yùn)用我們剛才的結(jié)論求解此類(lèi)求和問(wèn)題。”說(shuō)罷老C又在白板上繼續(xù)比劃起來(lái)。

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

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

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