“雖然自然辯證法這個(gè)理論是絕對正確的，但是我總感覺對解決實(shí)際問題的幫助不是很大。”小P對老C說道。兩個(gè)人下了自然辯證法的課，向東2樓走去。一邊走小P一邊評論。
“呵呵，”老C笑道，“雖然我們平時(shí)分析問題都是在靜態(tài)情況下分析和解決，但是，無論如何辯證法告訴我們這樣有可能是不正確的。因?yàn)槿祟愂苤橇ο拗疲荒?
在靜止的，片面的角度去分析問題——如果一次考慮了太多的外界因素，使用運(yùn)動(dòng)的觀點(diǎn)去看問題，反而會導(dǎo)致問題過于復(fù)雜以至于無法分析和解決。但是我們在解
決問題以后也不要忘記在實(shí)踐中去檢驗(yàn)我們的解決問題的方法，因?yàn)椤q證法告訴我們——我們的解法雖然在理論上成立，但前提——我們是在一個(gè)割裂的和靜態(tài)
的環(huán)境中去考慮問題的——好像有可能是不恰當(dāng)?shù)摹?#8221;
“哦？”小P點(diǎn)頭，“就是說辯證法最重要的作用是……提醒我們請?jiān)趯?shí)踐中檢查我們的理論……呵呵。”他騷騷一笑，“感覺辯證法的作用更像是一個(gè)錯(cuò)誤分析理
論，用來告訴我們錯(cuò)誤是怎樣發(fā)生的以及為什么會發(fā)生這種錯(cuò)誤，但是好像并不能非常有效的指導(dǎo)我們避免錯(cuò)誤，因?yàn)橐勒者@種理論去解決問題，好像就會陷入太多
的細(xì)節(jié)，需要考慮的因素太多，反而無法開始工作了……”
“呵呵，”老C笑道，“那么我們就先靜態(tài)的、割裂的解決一個(gè)問題先。”說著兩個(gè)人走進(jìn)了教研室，他從角落里拉過來白板。“漢諾塔的故事你聽說過吧？”老C問。
“嗯，這個(gè)題目我以前也做過，怎么？”小P問。
“那樣更好，我就不用多費(fèi)口舌了。”老C說道，“現(xiàn)在的問題是，請你求解一下解決這個(gè)問題，總共需要多少步。不要死記硬背以前記過的公式，我知道你以前做
過，我們需要從原理一步一步推導(dǎo)下去，這樣才更有意義一些。”他攔住急于在白板上寫寫畫畫的小P，說道，“我們需要講究一些方法，也是一般我們解決問題的
思路，現(xiàn)在我們就照這個(gè)思路來進(jìn)行。”
“哦？按照什么樣的思路？”小P問。
“我們可以這樣想象一下，我們所有已經(jīng)掌握的知識就像工具箱，一個(gè)一個(gè)排列在我們的右手；我們面對的問題也是一個(gè)一個(gè)的小箱子，排列在我們的左手。我們首
先要熟悉我們的工具箱，知道工具箱里面的工具是應(yīng)對什么問題的，應(yīng)當(dāng)如何被使用——比如我們需要了解一個(gè)活動(dòng)扳手是如何擰緊螺母的；然后我們左手的問題箱
子需要被分類，歸結(jié)到我們可以依靠工具箱解決的一類與依靠我們目前的工具箱無法解決的一類——比如我們看到螺絲，就會想到用螺絲刀，而看到螺母，就會想到
用扳手，如果我們可以正確的對問題分類，對于可以使用工具箱中的工具解決的問題，那么從右手邊的工具箱中拿出工具——解決問題就行了；然后我們需要在實(shí)踐
中再檢驗(yàn)一下我們解決問題的效果，根據(jù)反饋的信息再對問題進(jìn)行進(jìn)一步的細(xì)分種類，選擇更加合適的工具——如此循環(huán)，直到問題被解決的程度可以被接受為止。
”老C開始長篇大論，“所以解決問題的過程實(shí)際是逆向思維的過程，一般來說逆向思維都帶有嘗試的性質(zhì)，試的好不好，那要看你的個(gè)人經(jīng)驗(yàn)和悟性。”
“那么對于無法使用工具箱解決的問題呢？”小P說道。
“呵呵，那就需要一些創(chuàng)造性的勞動(dòng)了。”老C回答。“如果我們對已經(jīng)有的工具的原理足夠了解，我們就可以用這些工具來生產(chǎn)一些新的工具來解決新的問題。”
他吞了一口唾沫，“但是我們也需要對遇到的問題進(jìn)行足夠的了解——了解它的某些特質(zhì)，使得我們制造工具的活動(dòng)不會變得很盲目。”
“是嗎？”小P問，“那么如何開始呢？”
“首先我們先簡化問題，比如這個(gè)漢諾塔問題，我們可以先在3、5個(gè)碟子的情況下玩一玩，尋找一些規(guī)律。然后再考慮考慮此類問題如何被解決，通法是什么。”
他撓撓頭，“呵呵，那么我們就開始吧。由于我智力有限，一時(shí)無法理解n個(gè)盤子的漢諾塔問題，我們就先從3個(gè)盤子開始好不？盤子3表示最大的，在最底下，盤
子1表示最小的，在最上面；同樣我們也需要對桿子編號，最左面的叫1號，最右面的叫3號，你自己想想2號桿在什么地方……”
“……好啊好啊，那么我們就先來試試吧。”說著小P在白板上畫了起來。
“呵呵，畫的不好，像樹枝穿便便……”小P謙虛道。
“……”老C一時(shí)無語。過了一陣子，老C止住惡心，問道，“你看看這幾副圖，有沒有發(fā)現(xiàn)什么規(guī)律？”
“哦？什么意思？會有什么規(guī)律呢？”小P問。
“可能現(xiàn)在圖太多了，讓我們抽象一些，我來擦掉幾副圖。”老C說道，然后他在白板上將某些圖擦去。
“唔……”小P盯著看了一會兒，說道，“好像是經(jīng)過某些步數(shù)，將1號與2號盤子放到中間的桿子上，再將3號盤子放在最右邊的3號桿子上，然后再經(jīng)過某些步
數(shù)，將1號和2號在放到3號桿子上。”他想了想，道，“如果這樣看的話，好像移動(dòng)3個(gè)盤子的問題變?yōu)椋簩蓚€(gè)盤子移到第2個(gè)桿子，將3號盤子移到第3個(gè)桿
子，再將這兩個(gè)盤子移到第3個(gè)桿子。”
“是的，的確是這樣。”老C贊嘆，“如果我用Tn表示從一個(gè)桿子移動(dòng)n個(gè)盤子到另一個(gè)桿子——比如從1號移到3號桿，所需要的步數(shù)，那么我們會得到什么呢？”
“唔……”小P想了想，“好像是這樣，先將上面的(n-1)個(gè)盤子移到……無論什么地——比如說2號桿吧……這將需要Tn-1步，將最底下的第n個(gè)盤子從1號桿移到3號，這需要1步，再將那(n-1)個(gè)盤子從幫忙的桿子上移到我們的3號桿，還是需要Tn-1步……這樣我們得到Tn = Tn-1 + 1 +
Tn-1 = 2Tn-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 = 0……因?yàn)槿绻?個(gè)盤子需要移動(dòng)，我們什么都不用做，步數(shù)自然就是0了。”他繼續(xù)說道，“這樣我們就有了一組遞推數(shù)列。”于是他在白板上寫下了如下的公式。
T0 = 0
Tn = 2Tn-1 + 1
“看看，這樣問題就變?yōu)閷⑦@個(gè)遞推公式轉(zhuǎn)變?yōu)橥?xiàng)公式了。”老C說道，“發(fā)揮你強(qiáng)悍的數(shù)學(xué)知識，解決這個(gè)問題吧！”然后他幸災(zāi)樂禍的躲到一邊喝茶。
“切，這個(gè)算什么，小case啦！”小P嘴硬道，“這些東西我高中就會玩了。”于是他拿起一支筆，在白板上涂涂抹抹起來，“唔，這樣……然后這樣……不對不對……應(yīng)當(dāng)這樣……嗯……”
沒有理會小P的自言自語，老C慢慢的喝著茶水，跑去起點(diǎn)上看起了水文。
半個(gè)小時(shí)后……
“嗷！”小P突然喊道。
“干什么！你……”老C嚇得從椅子上跳了起來。
“我知道怎么做了！”小P興奮的說道。
“哦？”老C覺得這個(gè)小家伙還是比較強(qiáng)悍的，“你是怎么做的？這么快就做出來啦？”
“嘿嘿，”小P得意的說，“只要在兩邊同時(shí)處以2n就可以將問題轉(zhuǎn)化為求一個(gè)隊(duì)列的前n項(xiàng)和的問題。”說罷他指著白板上的一些演算。
Tn / 2n = 2Tn-1 / 2n + 2-n
Tn / 2n = Tn-1 / 2n－1 + 2-n
令Sn = Tn / 2n，則S0 = T0 / 20
= 0
那么原式可以轉(zhuǎn)化為：
S0 = 0
Sn = Sn-1 + 2-n
這個(gè)是等比數(shù)列an = 2-n 數(shù)列前n項(xiàng)求和(n >= 1)。所以利用等比數(shù)列求和公式，
又Sn = Tn / 2n，所以
Tn = 2n * Sn = 2n(1 – 2-n)
= 2n – 1
所以
Tn = 2n – 1
“看就是這樣求出來的。”小P得意的說道。
“呵呵，你是怎么想到要用等比數(shù)列求和的呢？”老C問。
“因?yàn)?#8230;…我只知道等差數(shù)列和等比數(shù)列的求和公式，我總要把問題轉(zhuǎn)化到我可以求解的范圍內(nèi)部啊，這樣才可以求解。”小P說道。
“呵呵，你的想法很好啊，知道用已經(jīng)掌握的工具去制造新的工具來解決問題，不錯(cuò)不錯(cuò)……但是美中不足的是在這一過程中充滿了技巧和構(gòu)造，對于編程人員來
說，他們是比較不喜歡技巧和構(gòu)造的巧合的東西，因?yàn)檫@些比較難以編程實(shí)現(xiàn)。”老C打擊了一下小P，“不過你還是很厲害啊，這樣都可以想出來。”老C又補(bǔ)了
一顆糖。
“……”小P一時(shí)不知道該說些什么。
“好吧，現(xiàn)在我們使用超級無敵蠻力計(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è)極其簡單的函數(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評論，“但是為了更加深入的了解到遞歸本身，我們還需要再繼續(xù)深入的討論一些其他的相關(guān)問題。”說罷他在白板上寫下一組公式。
anTn = bnTn-1 + Cn
“看，這個(gè)就是我們會遇到的某些遞歸問題的一種更一般的形式，其中an，bn和cn都是值隨著n變化的系數(shù)，而Tn是我們希望求解的數(shù)列通項(xiàng)。”老C說道，“如果讓我們一開始就求解這個(gè)東東，那么也太難了，我們先來解決一個(gè)更簡化一些的問題——這也是我們解決問題時(shí)通常的思路——來找找靈感，看會帶來一些思索的線索。”
T0 = α
Tn = Tn-1 + β + γn
“看，我們簡化了這個(gè)問題，使得遞推的增長項(xiàng)成為一個(gè)n的線性項(xiàng)，這樣就可以大大簡化剛才的問題。”老C道，“不要厭惡希臘字母，我相信你在數(shù)學(xué)書上看到
的希臘字母的次數(shù)絕對不會超過史詩級懸疑恐怖戰(zhàn)爭愛情巨作《伯羅奔尼撒戰(zhàn)記》的原本……但是，雖然問題被簡化了，但是像我這種智力水平底下的人，還是無法
理解的，所以我要試著代入幾個(gè)n的值，看看究竟會有什么樣子的規(guī)律。”說著他在白板上擦出一大片的空白，開始在上面寫東西。
T0 = α
T1 = T0 + β + γ
T2 = T1 + β + 2γ = (T0
+ β + γ) +β + 2γ = α+ 2β
+ 3γ
T3 = T2 + β + 3γ = (T0
+ 2β + 3γ) +β + 3γ = α + 3β + 6γ
“看……”老C說道，“我們似乎可以發(fā)現(xiàn)，其實(shí)Tn可以被分解為3個(gè)數(shù)列的和。”說完，他在白板的醒目位置寫下如下的式子。
T0 = α
Tn = αAn + βBn + γCn
“就是說我們認(rèn)為，如果隊(duì)列Tn可以表示為T0 =α; Tn =αAn + βBn + γCn 的形式，那么對于任意的α、β和γ，只要α、β、γ這3個(gè)參數(shù)的值被確定，那么Tn一定也可以被表示為T0 = α; Tn = Tn-1 + β + γn 的形式。”
“……的確是這樣啊，你這樣將問題反過來描述一下，有什么意義呢？”小P不解。
“呵呵，也就是說如果An、Bn、Cn的通項(xiàng)被確定和α、β、γ的值被確定，那么Tn就被確定；其中An、Bn、Cn是不變的數(shù)列，而α、β、γ是可以任意變化的參數(shù)，對應(yīng)不同的α、β、γ，Tn會具有不同的形式。”
“……這些我都已經(jīng)了解了……”小P嘟嘟囔囔。
“看看……”老C沒有理會小P的嘟囔，“這就是一個(gè)典型的待定系數(shù)問題，如果我們將An、Bn、Cn看作系數(shù)，而將α、β、γ看作變量，通過給出不同的α、β、γ值和對應(yīng)的Tn值，就可以求出相應(yīng)的An、Bn、Cn。”
“哦？”小P停止了心不在焉，“那么怎么才可以根據(jù)α、β、γ的值找到對應(yīng)的Tn值，然后反過來求出An、Bn、Cn呢？”
“可以先找到一個(gè)特定的Tn通項(xiàng)，再根據(jù)T0 = α 和Tn = Tn-1 + β + γn 來猜測此Tn對應(yīng)的α、β、γ。好處是我們把根據(jù)α、β、γ和Tn = Tn-1 + β + γn 來猜測Tn的過程反了過來，因?yàn)閺?#945;、β、γ和Tn = Tn-1 + β + γn 來猜測Tn的過程是逆向思維，然而從Tn通項(xiàng)和T0 = α、Tn = Tn-1 + β + γn來猜測Tn對應(yīng)的α、β、γ是正向思維——一般來說正向思維會比對應(yīng)的逆向思維來得簡單許多啊。接下來的工作就是根據(jù)我們猜測的結(jié)果對An、Bn、Cn求解。”
“那么應(yīng)當(dāng)怎么解呢？”小P問道。
“其實(shí)就是和一般的待定系數(shù)法的思想是一樣的，給出一個(gè)我們已經(jīng)知道的特解——這個(gè)解一般都是比較容易看出來或者推導(dǎo)出來的——將這個(gè)特解代入原方程，并
化簡，可以得到一個(gè)關(guān)于系數(shù)的方程；再猜測一個(gè)特解，代入原方程，化簡后又得到一個(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ù)法一樣，我們可以試著從最簡單的情況開始。”老C說，“我可以先假設(shè)Tn是一個(gè)常數(shù)數(shù)列，它的通項(xiàng)就是Tn = c，那么根據(jù)T0 = α，我們可以得到α = c；根據(jù)Tn = Tn-1 + β + γn，可以得到c = c + β + γn，根據(jù)這個(gè)式子，我們可以得到一個(gè)解——解可能有很多個(gè)，但是我們只要得到一組解就可以了——β = 0，γ ＝ 0；這樣我們根據(jù)Tn的通項(xiàng)公式Tn =αAn + βBn + γCn就知道了在α = c，β = 0，γ ＝ 0的情況下，Tn是一個(gè)常數(shù)數(shù)列Tn = c，而在α = c，β = 0，γ ＝ 0的情況下Tn = αAn + βBn + γCn可以化簡為Tn = cAn，而Tn實(shí)際上是Tn = c，所以c = cAn，所以An = 1。”
“哦？如果你把過程寫在白板上，我可能會更清楚一些。”小P說道。
“好的。”老C一邊答應(yīng)小P，一邊將推導(dǎo)的過程記錄在白板上，“在這里我們先找到一個(gè)特解，由于這個(gè)特解是如此的特殊，當(dāng)我們將這個(gè)解代入原方程——就是Tn =αAn + βBn + γCn后，不用再通過聯(lián)立后面2個(gè)方程解方程組，系數(shù)An就很容易的被求出來了……買糕的佛祖，這個(gè)特解找的也太nb了。”
“……是啊是啊……”小P奇怪自己怎么就找不到這樣一個(gè)奇妙的特解，“你還可以再找到2個(gè)特解嗎？因?yàn)槲覀冞€有2個(gè)待定的系數(shù)需要求解。”他問道。
“嘻嘻，其實(shí)就是運(yùn)氣好，恰好猜出來而已。”老C謙虛的說，“不過猜也要有道理的猜，我們解決實(shí)際問題其實(shí)就是在有道理的猜嘛……”說著他又在白板上演算起來。“我們的第2個(gè)特解，是Tn = n，因?yàn)門n = n可以表示成為n = (n-1) + 1，即Tn = Tn-1 + 1，所以我們的第2個(gè)特解很輕松的就出來了，根據(jù)Tn = Tn-1 + β + γn，我們可以猜測在Tn = n時(shí)，β = 1，γ = 0。而由Tn
= n和T0 = α，我們猜測α = 0也就很是合情合理了。所以我們又神奇的得到第2個(gè)特解：Tn = n，α = 0，β = 1，γ = 0。現(xiàn)在我們要做的就是將這個(gè)特解代入原方程Tn = αAn + βBn + γCn，來得到我們的第2個(gè)關(guān)于An、Bn、Cn的方程。”
“呵呵，這個(gè)步驟就由我來完成吧。”小P忍不住也想比劃比劃，“這樣將Tn = n，α = 0，β = 1，γ = 0代入原方程，我們得到n
= Bn，不會吧，Bn也這么容易的就求出來了？”小P有些佩服老C的rp了。
“嗯，看來我們的rp保持了較高的水準(zhǔn)。”老C贊嘆道，“下一組我決定使用Tn = n2，因?yàn)閚2 = (n - 1)2 – 1 + 2n，所以Tn可以表示為Tn = Tn-1
-1 +2n，根據(jù)Tn = Tn-1 + β + γn，我們又可以很輕易的猜測出β
= -1，γ ＝ 2，根據(jù)T0 = α可以得到α = T0 = 02 = 0，這樣第3個(gè)特解就是Tn = n2，α = 0，β = -1，γ ＝ 2……”
“我來我來……”小P道，他一邊說，一邊在白板上演算，“將Tn = n2，α = 0，β = -1，γ ＝ 2代入原方程Tn
= αAn + βBn
+ γCn，得到n2
= -Bn + 2Cn，看來在這里我們還需要和先前的2個(gè)系數(shù)方程進(jìn)行聯(lián)立了，不過也很簡單，因?yàn)橐呀?jīng)求出Bn = n了，代入n2 = -Bn
+ 2Cn，得到n2 = -n + 2Cn，所以Cn = n(n + 1)/2。”
“現(xiàn)在我們可以總結(jié)一下啦，如果一個(gè)數(shù)列具有T0
= α，Tn = Tn-1
+ β + γn的遞推公式，那么它的通項(xiàng)總可以寫為T0 = α，Tn = α + β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道，“我們先去吃飯，等回來我們再做一些練習(xí)來熟悉這個(gè)工具，為以后的應(yīng)用做些準(zhǔn)備。”
(這不是他們今天談?wù)摰乃袃?nèi)容)