第十四講遞推方法

1、第十四講 遞推方法遞推方法是人們從開始認(rèn)識(shí)數(shù)量關(guān)系時(shí)就很自然地產(chǎn)生的一種推理思想。例如自然數(shù)中最小的數(shù)是1，比1大1的數(shù)是2，接下來比2大1的數(shù)是3，由此得到了自然數(shù)數(shù)列：1，2，3，4，5，。在這里實(shí)際上就有了一個(gè)遞推公式，假設(shè)第n個(gè)數(shù)為an，則an1=an1即由自然數(shù)中第n個(gè)數(shù)加上1，就是第n1個(gè)數(shù)。由此可得：an2=an11這樣就可以得到自然數(shù)數(shù)列中任何一個(gè)數(shù)。再看一個(gè)例子：例1 平面上5條直線最多能把圓的內(nèi)部分成幾部分？平面上100條直線最多能把圓的內(nèi)部分成幾部分解：假設(shè)用ak表示k條直線最多能把圓的內(nèi)部分成的部分?jǐn)?shù)。這里k=0，1，2，。如圖可見a0=1a1= a01=2a2=a12

2、=4a3=a23=7a4= a34=11歸納出遞推公式an1=ann. (1即畫第n1條直線時(shí)，最多增加n部分。原因是這樣的：第一條直線最多把圓分成兩部分，故a1=2。當(dāng)畫第二條直線時(shí)，要想把圓內(nèi)部分割的部分盡可能多，就應(yīng)和第一條直線在圓內(nèi)相交，交點(diǎn)把第二條直線在圓內(nèi)部分分成兩條線段，而每條線段又把原來的一個(gè)區(qū)域劃分成兩個(gè)區(qū)域，因而增加的區(qū)域數(shù)是2，正好等于第二條直線的序號(hào)。同理，當(dāng)畫第三條直線時(shí)，要想把圓內(nèi)部分割的部分?jǐn)?shù)盡可能多，它就應(yīng)和前兩條直線在圓內(nèi)各有一個(gè)交點(diǎn)。兩個(gè)交點(diǎn)把第三條直線在圓內(nèi)部分成三條線段。而每條線段又把原來一個(gè)區(qū)域劃分成兩個(gè)區(qū)域。因而增加的區(qū)域部分?jǐn)?shù)是3，正好等于第三條直

3、線的序號(hào)，。這個(gè)道理適用于任意多條直線的情形，所以遞推公式（1）是正確的。這樣就易求得5條直線最多把圓內(nèi)分成：a5=a4+5=11+5=16（部分）要想求出100條直線最多能把圓內(nèi)分成多少區(qū)域，不能直接用上面的公式了，可把上面的遞推公式變形： an=an-1+n=an-2+(n-1+n=an-3+(n-2+(n-1+n=1+1+2+n=1+ (2 a100=1+=5051（部分）公式（2）也稱為數(shù)列1，2，4，7，11，16，的通項(xiàng)公式。一般來說，如果一個(gè)與自然數(shù)有關(guān)的數(shù)列中任一項(xiàng)an可以由它前面的k(n-1項(xiàng)經(jīng)過運(yùn)算或其他方法表示出來，我們就稱相鄰之間有遞歸關(guān)系，并稱這種公式為遞推公式或遞推

4、關(guān)系式。通過尋求遞歸關(guān)系來解決問題的方法就稱為遞推方法。許多與自然數(shù)有關(guān)的數(shù)學(xué)問題都常常具有遞推關(guān)系，可以用遞推公式來表達(dá)它的數(shù)量關(guān)系。如何尋求這個(gè)遞推公式是解決這類問題的關(guān)鍵之一，常用的方法是“退”到問題最簡單情況開始觀察，逐步歸納并猜想一般的遞推公式。在小學(xué)階段，我們僅要求學(xué)生能撥開問題的一些表面現(xiàn)象由簡到繁地歸納出問題的遞推公式就行了，不要求嚴(yán)格證明。當(dāng)然能證明更好。所謂證明，就是要嚴(yán)格推出你建立的關(guān)系式適合所有的n，有時(shí)，僅僅在前面幾項(xiàng)成立的關(guān)系，不一定當(dāng)n較大時(shí)也成立。例2 平面上10個(gè)兩兩相交的圓最多能將平面分割成多少個(gè)區(qū)域？平面上1993個(gè)圓最多能將平面分割成多少個(gè)區(qū)域？解：設(shè)平

5、面上k個(gè)圓最多能將平面分割成ak部分，我們先“退”到最簡單的情形。如圖可見：a1=2,a2=4=2+2×1,a3=8=4+2×2,a4=14=8+2×3,an=an-1+2(n-1. (3(3是這個(gè)問題的遞推公式。再把它變形為當(dāng)n較大時(shí)也能方便求出結(jié)果的公式：an= an-1+2(n-1=an-2+2(n-2+(n-1=an-3+2(n-3+(n-2+(n-1=a1+2(1+2+3+n-2+n-1=2+2×=n2-n+2 a10=102-10+2=92（個(gè)）a1993=19932-1993+2=3970058（個(gè)）關(guān)于這個(gè)遞推公式成立的正確性分析與例1完

6、全類似。比如，第一個(gè)圓顯然將平面分為兩個(gè)區(qū)域；當(dāng)畫第二個(gè)圓時(shí)，應(yīng)與原來的一個(gè)圓有兩個(gè)交點(diǎn)，即被第一個(gè)圓截成兩段弧，而每一段弧將原來的每一個(gè)區(qū)域分成兩個(gè)區(qū)域，故區(qū)域數(shù)增加了2，即增加了原來圓的個(gè)數(shù)的2倍；當(dāng)畫第三個(gè)圓時(shí)，應(yīng)與原來的兩個(gè)圓共有4個(gè)交點(diǎn)，圓弧被截成4段，而每段弧又將原來的每個(gè)區(qū)域分成兩個(gè)區(qū)域，所以區(qū)域增加了4，即原來圓的個(gè)數(shù)的2倍，同理類推，說明遞推公式應(yīng)該是：an= an-1+2(n-1.例3 在一個(gè)圓周上按下面規(guī)則標(biāo)上一些數(shù)：第一次先把圓周二等分，在兩個(gè)分點(diǎn)旁標(biāo)上和，如圖(a。第二次把兩段半圓弧二等分，在分點(diǎn)旁標(biāo)上相鄰兩分點(diǎn)旁所標(biāo)兩數(shù)的和，如圖(b，標(biāo)上。第三次把4段圓弧分別二等

7、分，并在4個(gè)分點(diǎn)旁邊標(biāo)上兩個(gè)相鄰分點(diǎn)旁所標(biāo)數(shù)的和，如圖(c，分別標(biāo)上和。如此繼續(xù)下去，當(dāng)?shù)诎舜螛?biāo)完數(shù)以后，圓周上所有已標(biāo)的數(shù)的和是多少？解：我們一般地設(shè)第一次所標(biāo)的兩數(shù)分別為a、b，用Sk表示第k次標(biāo)完后各分點(diǎn)所標(biāo)數(shù)的和。如圖可見：S1=a+b, S2= S1+2 S1=3 S1=3(a+b.原因是這樣的：S2是兩類分點(diǎn)旁的標(biāo)數(shù)和，一類是原來分點(diǎn)所標(biāo)數(shù)的和S1，另一類是新增分點(diǎn)所標(biāo)數(shù)的和，它正好是由原來各分點(diǎn)所標(biāo)的數(shù)向左加一次，又向右加一次的和，故新增分點(diǎn)旁所標(biāo)數(shù)的和恰好是原來所有數(shù)之和的2倍2 S1，因此有：S2= S1+2 S1=3 S1，S3= S2+2 S2=3 S2=32 S1,S4

8、=32 S1+2×32 S1=33 S1,Sn=3n-1 S1=3n-1(a+b (4（4）式為遞推公式：Sn=3Sn-1在S1=a+b時(shí)已解出的表達(dá)式。所謂解出，即Sn直接直接依賴于n與S1而計(jì)算出，不再是Sn依賴于Sn-1，Sn-1又依賴于Sn-2這樣的形式。 當(dāng)n=8, a=, b=時(shí)，S8=37(+=2187×=.例4 假設(shè)剛出生的雌雄一對(duì)小兔過兩個(gè)月就能生下雌雄一對(duì)小兔，此后每月生下一對(duì)小兔。如果養(yǎng)了初生的一對(duì)小兔，問滿一年時(shí)共可得多少對(duì)兔子？解：我們先退到開始的簡單情況來推算，從中歸納出遞推關(guān)系。如圖：第一個(gè)月：只有1對(duì)小兔；第二個(gè)月：一對(duì)小兔長成一對(duì)大兔，但尚

9、不會(huì)生殖，仍只有一對(duì)兔子；第三個(gè)月：這對(duì)大兔生了一對(duì)小兔，這時(shí)共2對(duì)兔子；第四個(gè)月：大兔又生了一對(duì)小兔，而上月出生的小兔正在長大，這時(shí)共3對(duì)兔子；第五個(gè)月：這時(shí)已有兩對(duì)大兔可以生殖（原來的大兔和第三個(gè)月出生的小兔），于是生了兩對(duì)小兔，這時(shí)共有5對(duì)兔子。把推算的結(jié)果列成一張表：月份數(shù)一二三四五六七八九十十一十二十三兔子對(duì)數(shù)1123581321345589144233由表中可見滿一年時(shí)可得144對(duì)兔子。如果要算的時(shí)間長，這種方法就有困難了，現(xiàn)在我們來找遞推關(guān)系。用Un表示第n個(gè)月時(shí)的兔子對(duì)數(shù)，則：Un：1，1，2，3，5，8，13，21，34，容易發(fā)現(xiàn)遞推公式是：Un=Un-1+Un-2.現(xiàn)在說明

10、這個(gè)遞推公式是正確的。因?yàn)榈趎個(gè)月時(shí)的兔子對(duì)分兩類，一類是第n-1個(gè)月時(shí)的兔子對(duì)，另一類是當(dāng)月新生的兔子對(duì)，而這些小兔對(duì)數(shù)恰好是第n-2個(gè)月時(shí)的兔子對(duì)數(shù)Un-2。有了上面的遞推公式就可以寫出Un的第12項(xiàng)為144對(duì)，這正是本題要求的滿一年時(shí)的小兔總對(duì)數(shù)。數(shù)列Un稱為斐波那契數(shù)列（Fibonacci,11701250，是意大利數(shù)學(xué)家）。由于數(shù)列Un具有許多重要的奇特性質(zhì)，因而受到數(shù)學(xué)家們的極大關(guān)注，并把數(shù)列Un取名為斐波那契數(shù)列。例5 傳說在印度的佛教圣地貝拿勒斯圣廟里安放著一個(gè)黃銅板，板上插著三根寶石針，在第一根寶石針上，從下到上穿著由大到小的64片中心有孔的金片，每天都有一個(gè)值班僧侶按下面規(guī)

11、則移動(dòng)金片：把金片從第一根寶石針移到其余的寶石針上。要求一次只能移動(dòng)一片，而且小片永遠(yuǎn)要放在大片的上面。當(dāng)時(shí)傳說當(dāng)64片金片都按上面的規(guī)則從第一根寶石針移到另一根寶石針上時(shí)，世界將在一聲霹靂中毀滅。所以有人戲稱這個(gè)問題叫“世界末日”問題（也稱為“Hanoi塔”問題）。當(dāng)然，移金片和世界毀滅并無聯(lián)系，這只是一個(gè)傳說而已，但說明這是一個(gè)需要移動(dòng)很多很多次才能辦到的事情。解這個(gè)問題的方法在算法分析中也常用到。究竟按上述規(guī)則移動(dòng)完這64片金片需要移動(dòng)多少次呢解：設(shè)有n片金片，把從第一片金片至第k片金片按題目要求由第一根寶石針移到另一根寶石針共需ak次。先對(duì)4片金片的簡單情形，用下列的幾組圖來表示移動(dòng)過

12、程中的各種狀態(tài)，并計(jì)數(shù)，歸納出遞歸關(guān)系式。這節(jié)的前幾個(gè)例子都是“退”到簡單的特殊情況來歸納出一般規(guī)律，在這個(gè)例子里，我們將先用一般推理得出遞推公式，再以n=64代入，便可解決我們這個(gè)例題。這種從一般到特殊來解決問題的方法也是數(shù)學(xué)上的一種常用方法。我們可以這樣來想：為了移動(dòng)第n片到第根寶石針上，我們必須先把它上面的n-1片按題目的規(guī)則采用某種程序移到第根寶石針上，這需要移動(dòng)an-1次，然后才能把最下面第n片（最大的），移到第根寶石針上。最后再經(jīng)過an-1次才能把第根寶石針上的n-1片金片按上面規(guī)則采用同樣程序移到第根寶石針上。因此把n片金片按題中的規(guī)則全部移到另一根寶石針上共應(yīng)移：an=2an-

13、1+1（次） （5）這就是遞推公式。為了求得n=64時(shí)a64的值，我們當(dāng)然不能一次次地由a1=1,a2=3,a3=7,直到算出a64。現(xiàn)在我們?cè)O(shè)法把遞推公式（5）變形為可以直接計(jì)算a64的形式。 an=2an-1+1=2(2an-2+1=22an-2+2+1=22(2an-3+1+2+1=23an-3+22+21+1=2n-1a1+2n-2+2n-3+2+1=1+2+22+2n-2+2n-1 an=2an-an=2(1+2+22+2n-1-(1+2+22+2n-1=2n-1 a64=264-1.a64是一個(gè)非常大的數(shù)，如果按照每移動(dòng)一片需一秒鐘算，把64片金片從一根寶石針移到另一根寶石針上大約需要5800億年。習(xí) 題 十 四1，請(qǐng)你根據(jù)下列各個(gè)數(shù)之間的關(guān)系，在括號(hào)里填上恰當(dāng)?shù)臄?shù)：（1）1，5，9，13，17，（ ）。（2）0.625, 1.25, 2.5, 5, ( .（3），。（4）198，297，396，495，（ ），（ ）。2，將自然數(shù)1，2，3，按圖排列，在“2”處轉(zhuǎn)第一個(gè)彎，“3”處轉(zhuǎn)第二個(gè)彎