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

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

2、數(shù).這里 k0，1，2， .如圖可見。a0 1a1 =a0+12a2 =a1 2=4a3=a2 3=7a4=a3+4 11an 可以由它前面歸納出遞推公式 an 1an +n. （1）即畫第 n1 條直線時，最多增加 n 部分 .原因是這樣的：第一條直線最多把圓分成兩部分，故 a1 2.當畫第二條直線時要想把圓內(nèi)部分割的部分盡可能多，就應和第一條直線在圓內(nèi)相交， 交點把第二條直線在圓內(nèi)部分分成兩條線段， 而每條線段又把原來的一個區(qū)域劃分成兩個區(qū)域， 因而增加的區(qū)域數(shù)是 2，正好等于第二條直線的序號 .同理，當畫第三條直線時，要想把圓內(nèi)部分割的部分數(shù)盡可能多， 它就應和前兩條直線在圓內(nèi)各有一個交

3、點 .兩個交點把第三條線在圓內(nèi)部分成三條線段 .而每條線段又把原來一個區(qū)域劃分成兩個區(qū)域 .因而增加的區(qū)域部分數(shù)是 3，正好等于第三條直線的序號， .這個道理適用于任意多條直線的情形 .所以遞推公式 （ 1）是正確的 .這樣就易求得 5 條直線最多把圓內(nèi)分成：a5=a4+5 11=5 16（部分）。要想求出 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， 的通項公式 .一般來說，如果一個與自然數(shù)有關的數(shù)列

4、中的任一項的 k（ n-1）項經(jīng)過運算或其他方法表示出來， 我們就稱相鄰項之間有遞歸關系，并稱這個數(shù)列為遞歸數(shù)列 .如果這種推算方法能用公式表示出來，就稱這種公式為遞推公式或遞推關系式 .通過尋求遞歸關系來解決問題的方法就稱為遞推方法 .許多與自然數(shù)有關的數(shù)學問題都常常具有遞推關系，可以用遞推公式來表達它的數(shù)量關系.如何尋求這個遞推公式是解決這類問題的關鍵之一，常用的方法是“退”到問題最簡單情況開始觀察 .逐步歸納并猜想一般的速推公式 .在小學生階段，我們僅要求學生能撥開問題的一些表面現(xiàn)象由簡到繁地歸納出問題的遞推公式就行了， 不要求嚴格證明 .當然能證明更好 .所謂證明，就是要嚴格推出你建立

5、的關系式適合所有的 n，有時，僅僅在前面幾項成立的關系式，不一定當n 較大時也成立。例 2 平面上 10 個兩兩相交的圓最多能將平面分割成多少個區(qū)域？平面上 1993 個圓最多能將平面分割成多少個區(qū)域？解：設平面上 k 個圓最多能將平面分割成 ak 部分 .我們先“退”到最簡單的情形 .如圖可見a1 =2，a2=422× 1，a38=4 2× 2，a4=14=8+2×3，an =an-1 +2（n-1）.（ 3）（3）是這個問題的遞推公式 .再把它變形為當 n 較大時也能方便求出結(jié)果的公式：an an-1 +2（ n-1）an-2 +2（ n-2） +（ n-1）

6、 an-3 2 （ n-3） +（n-2） +（n-1） =a1+2（ 1+2+3+n-2+n-1）a10=102-10+2=92（個），a1 993=19932-1993 2=3970058（個）。關于這個遞推公式成立的正確性分析與例 1 完全類似 .比如，第一個圓顯然將平面分為兩個區(qū)域； 當畫第二個圓時， 應與原來的一個圓有兩個交點， 即被第一個圓截成兩段弧， 而每一段弧將原來的每一個區(qū)域分成兩個區(qū)域，故區(qū)域數(shù)增加了 2，即增加了原來圓的個數(shù)的 2 倍；當畫第三個圓時，應與原來的兩個圓共有 4個交點，圓弧被截成 4 段，而每段弧又將原來的每個區(qū)域分成兩個區(qū)域， 所以區(qū)域增加了 4，即原來圓

7、的個數(shù)的 2 倍， ，同理類推，說明遞推公式應該是an =an-1 +2（n-1）。例 3 在一個圓周上按下面規(guī)則標上一些數(shù)：第一次先把圓周二等分，三次把 4 段圓弧分別二等分， 并在 4 個分點旁邊標上兩個相鄰分點旁所去，當?shù)诎舜螛送陻?shù)以后，圓周上所有已標的數(shù)的和是多少？解：解：我們一般地設第一次所標的兩數(shù)分別為 a、b，用 Sk 表示第 k 次標完后各分點所標數(shù)的和 .如圖可見S1ab，S2 S1 +2S13S13（ab）。原因是這樣的： S2 是兩類分點旁的標數(shù)和，一類是原來分點所標數(shù)的和 S1，另一類是新增分點所標數(shù)的和， 它正好是由原來各分點所標的數(shù)向左加一次， 又向右加一次的和，

8、故新增分點旁所標數(shù)的和恰好是原來所有數(shù)之和的 2 倍 2S1，因此有S2=S12S1 =3S1，同理類推S3=S2+2S23S2=32S1，S432S12×32S132S1 ，Sn=3n-1 S1 =3n-1 （ a b） （4）（4）式為遞推公式： Sn 3Sn-1 在 S1=ab 時已解出的表達式 . 所謂解出，即 Sn 直接依賴于 n 與 S1 而計算出 .不再是 Sn 依賴于 Sn-1 ， Sn-1 又依賴于 Sn-2 這樣的形式。例 4 假設剛出生的雌雄一對小兔過兩個月就能生下雌雄一對小兔，此后每月生下一對小兔 .如果養(yǎng)了初生的一對小兔，問滿一年時共可得多少對兔子？解：我們

9、先退到開始的簡單情況來推算，從中歸納出遞推關系 .如圖：第一個月：只有 1 對小兔。第二個月：一對小兔長成一對大兔，但尚不會生殖 .仍只有一對兔子。第三個月：這對大兔生了一對小兔，這時共2 對兔子。第四個月：大兔又生了一對小兔，而上月出生的小兔正在長大，這時共 3 對兔子。第五個月：這時已有兩對大兔可以生殖 （原來的大兔和第三個月出生的小兔），于是生了兩對小兔，這時共有 5 對兔子。把推算的結(jié)果列成一張表由表中可見滿一年時可得144 對兔子。如果要算的時間長， 這種方法就有困難了， 現(xiàn)在我們來找遞推關系。用 un表示第 n 個月時的兔子對數(shù)，則un： 1， 1， 2， 3，5，8，13，21，

10、 34， 。容易發(fā)現(xiàn)遞推公式是un=un-1 +un-2 。現(xiàn)在說明這個遞推公式是正確的 .因為第 n 個月時的兔子對分兩類，一類是第 n-1 個月時的兔子對，另一類是當月新生的兔子對，而這些小兔對數(shù)恰好是第 n-2 個月時的兔子對數(shù) un-2 。有了上面的遞推公式就可以寫出 un的第 12 項為 144 對 .這正是本題要求的滿一年時的小兔總對數(shù)。數(shù)列 un稱為斐波那契數(shù)列（ Fibonacci， 11701250，是意大利數(shù)學家） .由于數(shù)列 un具有許多重要的奇特性質(zhì) .因而受到數(shù)學家們的極大關注，并把數(shù)列 un取名為斐波那契數(shù)列 .例 5 傳說在印度的佛教圣地貝拿勒斯圣廟里安放著個一個

11、黃銅板，板上插著三根寶石針， 在第一根寶石針上， 從下到上穿著由大到小的 64 片中心有孔的金片 .每天都有一個值班僧侶按下面規(guī)則移動金片：把金片從第一根寶石針移到其余的某根寶石針上 .要求一次只能移動一片， 而且小片永遠要放在大片的上面 .當時傳說當 64 片金片都按上面的規(guī)則從第一根寶石針移到另一根寶石針上時， 世界將在一聲霹靂中毀滅 .所以有人戲稱這個問題叫 “世界末日” 問題（也稱為“ Hanoi 塔”問題），當然，移金片和世界毀滅并無聯(lián)系，這只是一個傳說而已，但說明這是一個需要移動很多很多次才能辦到的事情 .解這個問題的方法在算法分析中也常用到 .究竟按上述規(guī)則移動完成 64 片金片

12、需要移動多少次呢？解：設有 n 片金片，把從第一片金片至第 k 片金片按題目要求由第 I 根寶石針移到另一根寶石針共需移動 ak 次。先對 4 片金片的簡單情形用下列的幾組圖來表示移動過程中的各種狀態(tài)，并計數(shù)，歸納出遞歸關系式。這節(jié)的前幾個例子都是 “退”到簡單的特殊情況來歸納出一般規(guī)律 .在這個例子里，我們將先用一般推理得出遞推公式， 再以 n=64 代入，便可解決我們這個例題 .這種從一般到特殊來解決問題的方法也是數(shù)學上的一種常用方法。我們可以這樣來想： 為了移動第 n 片到第根寶石針上， 我們必須先把它上面的 n-1 片按題目的規(guī)則采用某種程序移到第根寶石針上，這需要移動 an-1 次.

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

14、n-1 a12n-2 +2n-3 +2 1=1 222+2n-2 2n-1 ，an2an -an=2（ 1+2+22 +2n-1 ）-（ 1+2+2n-1 ）=2n-1，a64 264 -1。a64 是一個非常大的數(shù) .如果按每移動一片次需一秒鐘算，把 64 片金片從一根寶石針移到另一根寶石針上大約需要 5800 億年。有小學初中高中各科同步培優(yōu)的視頻和講義，和 word, 含答案。奧數(shù)講義也有，含答案，可以編輯。奧數(shù)競賽奧數(shù)強化希望杯華杯中環(huán)杯等等。奧數(shù)超常初中競賽視頻講義高中競賽視頻講義高中視頻講義都是最新的視頻講義語文閱讀寫作新概念聽說讀寫都有。468 453 607Wei xin 13

15、6 9977 1074可以加我習題十四1. 請你根據(jù)下列各個數(shù)之間的關系，在括號里填上恰當?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)第一個彎，“ 3” 處轉(zhuǎn)第二個彎，“ 5”處轉(zhuǎn)第三個彎， .問哪個數(shù)處轉(zhuǎn)第二十個彎？3.請用速推方法求出甲、乙、丙、丁四人站成一排照相，共有多少種不同站法？4.上一段 12 級樓梯，規(guī)定每一步只能上一級或兩級 .問要登上第 12 級樓梯共有多少種不同走法？5. 有 10 個村莊，分別用 A 1， A 2， ， A 10 表

16、示，某人從 A 1 出發(fā)按箭頭方向繞一圈最后經(jīng)由 A 10 再回到 A 1，有多少種不同走法？注：每點（村）至多過一次，兩村之間，可走直線，也可走圓周上弧線，但都必須按箭頭方向走 .習題十四解答1.相鄰兩數(shù)的差均為4，故括號里應填 17+421。 1.25-0.625=0.625，2. 5-1.25=1.25，3. 5-2.5=2.5，可見差正好等于減數(shù)。（ ）-55，（ ）=55=10。或者：后一個數(shù)為前一個數(shù)的2 倍，故括號里應填 2× 5=10。從數(shù)列可見分子從2 開始逐個增大 1；分母從 10 開始逐個增22，28， 34，40， 46，52，58。這個分數(shù)為第 9 個數(shù)。括

17、號里應填 10。十位上數(shù)不變，百位上數(shù)依次遞增 1，個位上數(shù)依次遞減 1，故括號中數(shù)應填 594，693。2.解：拐彎處數(shù)的規(guī)律可見下頁表。第 19 個拐彎處的數(shù)比第 18 個拐彎處的數(shù)大 10，第 20 個拐彎處的數(shù)比第 19 個拐彎處的數(shù)也大 10，故第 20 個拐彎處的數(shù)為：1+2×（ 1+2+3 10） 111。3.解：假設 n 個人站成一排共有 an 種不同站法 .可以先讓其中的 n-1 個人站成一排，共有 an-1 種不同的站法，再讓剩下的那個人站在他們中間或兩頭，又有 n 種站法 .由乘法原理，可得到遞推公式：an n×an-1 。又 a1 1，a4=4

18、15; a3 4×3× a2 =4×3×2×a1=4！ 24。4.解：設登上 n 級樓梯共有 an 種不同走法， n1，2， .把上到第 n 級樓梯的情形分為兩種走法 .一類是先上到第 n-1 級樓梯，然后再上一級，共有 an-1 種走法 .另一類是先上到第 n-2 級樓梯，然后再上兩級，共有 an-2 種走法 .由加法原理，上到第 n 級樓梯的走法 an 滿足下列遞推關系式：an =an-1 an-2 。又 a1=1，a2=2，故上樓梯方法數(shù)an 依次為 1，2，3，5，8，13，21，34，55， 89，144，233， .上到第 12 級樓梯共有 233 種不同走法。5.解：設從 A 1 按箭頭方向走到A n+1 的走法數(shù)為 an，n=1，2， ， 9.則 a9 即為所求（因為從 A 10 回到 A 1 只有一種方式） .可見， a1=1， a2 =2，ak 1=ak ak-1 為遞推公式。an（n1，2， ， 9）依次為 1，2，3，5，8，13，21，34， 55.即共 55 種不同的走法。