奧數(shù)遞推方法含答案

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，則an+1=an+1即由自然數(shù)中第n個(gè)數(shù)加上1，就是第n+1個(gè)數(shù)。由此可得an2=an11，這樣就可以得到自然數(shù)數(shù)列中任何一個(gè)數(shù)再看一個(gè)例子：例1 平面上5條直線最多能把圓的內(nèi)部分成幾部分？平面上100條直線最多能把圓的內(nèi)部分成幾部分？假設(shè)用ak表示k條直線最多能把圓的內(nèi)部分成的部分?jǐn)?shù).這里k0，1，2，.如圖可見。a01a1=a0+12a2=a12=

2、4a3=a23=7a4=a3+411歸納出遞推公式an1an+n. （1）即畫第n1條直線時(shí)，最多增加n部分.原因是這樣的：第一條直線最多把圓分成兩部分，故a12.當(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，正好等于第三條直線的序號(hào)

3、，.這個(gè)道理適用于任意多條直線的情形.所以遞推公式（1）是正確的.這樣就易求得5條直線最多把圓內(nèi)分成：a5=a4+511=516（部分）。要想求出100條直線最多能把圓內(nèi)分成多少區(qū)域，不能直接用上面公式了，可把上面的遞推公式變形：an=an-1+n=nn-2（n-1）n=an-3+（n-2）（n-n）+n 公式（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)算或其他方法表示出來，我們就稱相鄰項(xiàng)之間有遞歸關(guān)系，并稱這個(gè)數(shù)列為遞歸數(shù)列.如果這種推算方法能用公式表示出來，就稱這種公式為遞推公式或遞推關(guān)系式.通

4、過尋求遞歸關(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è)平面上k

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

6、域；當(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ù)：第一次先把圓周二等分，三次把4段圓弧分別二等分，并在4個(gè)分點(diǎn)旁邊標(biāo)上兩個(gè)相鄰分點(diǎn)旁所去，當(dāng)?shù)诎舜螛?biāo)完數(shù)以后，圓周上所有已標(biāo)的數(shù)的和是多少？解：解：我們一般地設(shè)第一次所標(biāo)的兩數(shù)分別為a、b，用Sk表示第

7、k次標(biāo)完后各分點(diǎn)所標(biāo)數(shù)的和.如圖可見S1ab，S2S1+2S13S13（ab）。原因是這樣的：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倍2S1，因此有S2=S12S1=3S1，同理類推S3=S2+2S23S2=32S1，S432S12×32S132S1，Sn=3n-1S1=3n-1（ab） （4）（4）式為遞推公式：Sn3Sn-1在S1=ab時(shí)已解出的表達(dá)式.所謂解出，即Sn直接依賴于n與S1而計(jì)算出.不再是Sn依賴于Sn-1，Sn-1又

8、依賴于Sn-2這樣的形式。 例4 假設(shè)剛出生的雌雄一對(duì)小兔過兩個(gè)月就能生下雌雄一對(duì)小兔，此后每月生下一對(duì)小兔.如果養(yǎng)了初生的一對(duì)小兔，問滿一年時(shí)共可得多少對(duì)兔子？解：我們先退到開始的簡單情況來推算，從中歸納出遞推關(guān)系.如圖：第一個(gè)月：只有1對(duì)小兔。第二個(gè)月：一對(duì)小兔長成一對(duì)大兔，但尚不會(huì)生殖.仍只有一對(duì)兔子。第三個(gè)月：這對(duì)大兔生了一對(duì)小兔，這時(shí)共2對(duì)兔子。第四個(gè)月：大兔又生了一對(duì)小兔，而上月出生的小兔正在長大，這時(shí)共3對(duì)兔子。第五個(gè)月：這時(shí)已有兩對(duì)大兔可以生殖（原來的大兔和第三個(gè)月出生的小兔），于是生了兩對(duì)小兔，這時(shí)共有5對(duì)兔子。把推算的結(jié)果列成一張表由表中可見滿一年時(shí)可得144對(duì)兔子。如果要

9、算的時(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?，F(xiàn)在說明這個(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ù)列u

10、n取名為斐波那契數(shù)列.例5 傳說在印度的佛教圣地貝拿勒斯圣廟里安放著個(gè)一個(gè)黃銅板，板上插著三根寶石針，在第一根寶石針上，從下到上穿著由大到小的64片中心有孔的金片.每天都有一個(gè)值班僧侶按下面規(guī)則移動(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è)問題的方法在算法分析中也常用到

11、.究竟按上述規(guī)則移動(dòng)完成64片金片需要移動(dòng)多少次呢？解：設(shè)有n片金片，把從第一片金片至第k片金片按題目要求由第I根寶石針移到另一根寶石針共需移動(dòng)ak次。先對(duì)4片金片的簡單情形用下列的幾組圖來表示移動(dòng)過程中的各種狀態(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次.然后才能把最下

12、面第n片（最大的），稱到第根寶石針上.最后再經(jīng)過an-1次才能把第根寶石針上的n-1片金片按上面規(guī)則采用同樣程序移到第根寶石針上.因此把n片金片按題中的規(guī)則全部移到另一根寶石針上共應(yīng)移an=2an-1+1（次）. （5）這就是遞推公式。為了求得n=64時(shí)a64的值，我們當(dāng)然不能一次次地由a1=1，a2=3，a3=7，直到算出a64.現(xiàn)在我們設(shè)法把遞推公式（5）變形為可以直接計(jì)算a64的形式。an=2an-1+1=2（2an-21）+1=22an-2+21=22（2an-3+1）+2+123an-322+21+1=2n-1a12n-2+2n-3+21=1222+2n-22n-1，an2an-an

13、=2（1+2+22+2n-1）-（1+2+2n-1）=2n-1，a64264-1。a64是一個(gè)非常大的數(shù).如果按每移動(dòng)一片次需一秒鐘算，把64片金片從一根寶石針移到另一根寶石針上大約需要5800億年。 有小學(xué)初中高中各科同步培優(yōu)的視頻和講義，和word,含答案。奧數(shù)講義也有，含答案，可以編輯。奧 數(shù) 競 賽 奧 數(shù) 強(qiáng) 化 希 望 杯 華 杯 中環(huán)杯 等等。奧 數(shù) 超 常初中競賽視頻講義 高中競賽視頻講義 高中視頻講義都是最新的視頻講義 語文閱讀寫作 新概念 聽說讀寫 都有。 468 453 607 Wei xin 136 9977 1074可以加我習(xí)題十四1.請(qǐng)你根據(jù)下列各個(gè)數(shù)之間

14、的關(guān)系，在括號(hào)里填上恰當(dāng)?shù)臄?shù)：1，5，9，13，17，（ ）。0.625，1.25，2.5，5，（ ）。198，297，396，495，（ ），（ ）。2.將自然數(shù)1，2，3，按圖排列，在“2”處轉(zhuǎn)第一個(gè)彎，“3”處轉(zhuǎn)第二個(gè)彎，“5”處轉(zhuǎn)第三個(gè)彎，.問哪個(gè)數(shù)處轉(zhuǎn)第二十個(gè)彎？3.請(qǐng)用速推方法求出甲、乙、丙、丁四人站成一排照相，共有多少種不同站法？4.上一段12級(jí)樓梯，規(guī)定每一步只能上一級(jí)或兩級(jí).問要登上第12級(jí)樓梯共有多少種不同走法？5.有10個(gè)村莊，分別用A1，A2，A10表示，某人從A1出發(fā)按箭頭方向繞一圈最后經(jīng)由A10再回到A1，有多少種不同走法？注：每點(diǎn)（村）至多過一次，兩村之間，可走直

15、線，也可走圓周上弧線，但都必須按箭頭方向走. 習(xí)題十四解答1.相鄰兩數(shù)的差均為4，故括號(hào)里應(yīng)填17+421。1.25-0.625=0.625，2.5-1.25=1.25，3.5-2.5=2.5，可見差正好等于減數(shù)。（ ）-55，（ ）=55=10?；蛘撸汉笠粋€(gè)數(shù)為前一個(gè)數(shù)的2倍，故括號(hào)里應(yīng)填2×5=10。從數(shù)列可見分子從2開始逐個(gè)增大1；分母從10開始逐個(gè)增22，28，34，40，46，52，58。這個(gè)分?jǐn)?shù)為第9個(gè)數(shù)。括號(hào)里應(yīng)填10。十位上數(shù)不變，百位上數(shù)依次遞增1，個(gè)位上數(shù)依次遞減1，故括號(hào)中數(shù)應(yīng)填594，693。2.解：拐彎處數(shù)的規(guī)律可見下頁表。第19個(gè)拐彎處的數(shù)比第1

16、8個(gè)拐彎處的數(shù)大10，第20個(gè)拐彎處的數(shù)比第19個(gè)拐彎處的數(shù)也大10，故第20個(gè)拐彎處的數(shù)為：1+2×（1+2+310）111。3.解：假設(shè)n個(gè)人站成一排共有an種不同站法.可以先讓其中的n-1個(gè)人站成一排，共有an-1種不同的站法，再讓剩下的那個(gè)人站在他們中間或兩頭，又有n種站法.由乘法原理，可得到遞推公式：ann×an-1。又a11，a4=4×a34×3×a2=4×3×2×a1=4！24。4.解：設(shè)登上n級(jí)樓梯共有an種不同走法，n1，2，.把上到第n級(jí)樓梯的情形分為兩種走法.一類是先上到第n-1級(jí)樓梯，然后再上一級(jí)，共有an-1種走法.另一類是先上到第n-2級(jí)樓梯，然后再上兩級(jí)，共有an-2種走法.由加法原理，上到第n級(jí)樓梯的走法an滿足下列遞推關(guān)系式：an=an-1an-2。又a1=1，a2=2，故上樓梯方法數(shù)an依次為1，2，3，5，8，13，21，34，55，89，144，233，.上到第12級(jí)樓梯共有233種不同走法。5.解：設(shè)從A1按箭頭方向走到An+1的走法數(shù)為an，n=1，2，9.則a9即為所求（因?yàn)閺腁10回到A1只有一種方式）.可見，a1=1，a2=2，ak1=akak-1為遞推公式。an（n1，2，9）依次為