本文格式為Word版，下載可任意編輯——遞推法的應(yīng)用遞推法的應(yīng)用

廣東石油化工學(xué)院高州師范學(xué)院309數(shù)學(xué)（4）班梁彥清

遞推的思想方法是數(shù)學(xué)中重要和基本的思想方法。小學(xué)生寫自然數(shù)的過(guò)程就運(yùn)用了簡(jiǎn)單的遞推關(guān)系。中學(xué)數(shù)學(xué)里，好多與自然數(shù)有關(guān)的命題往往要用遞推法。如重要的數(shù)學(xué)歸納法，實(shí)際上是遞推法的思想方法。遞推關(guān)系遞推法遞推公式在紛繁變幻的世界，所有事物都隨時(shí)間的流逝發(fā)生著微妙的變化。而大量現(xiàn)象的變化是有規(guī)律可循的，這種規(guī)律往往浮現(xiàn)出前因和后果的關(guān)系。即是說(shuō)，某種現(xiàn)象的變化結(jié)果與緊靠它前面變化的一個(gè)或一些結(jié)果緊湊關(guān)聯(lián)。而遞推關(guān)系的思想正表達(dá)了這一規(guī)律。遞推關(guān)系不僅對(duì)組合論有重要的意義，而且?guī)缀鯇?duì)一切數(shù)學(xué)分支都有重要的意義。遞推關(guān)系在算法分析中占有很重要的地位。學(xué)好遞推關(guān)系不僅可以提高我們的數(shù)學(xué)素養(yǎng)，更對(duì)今后進(jìn)行數(shù)學(xué)研究有舉足輕重的作用。本文將圍圍著遞推關(guān)系的廣泛應(yīng)用及其表達(dá)出的遞推思想展開論述。

一、對(duì)“遞推法和遞推關(guān)系〞的概述1．遞推法的概念

遞推法是根據(jù)具體問(wèn)題，建立遞推關(guān)系，在通過(guò)遞推關(guān)系求解的方法。期中遞推關(guān)系是表示關(guān)于正整數(shù)參變量的一類特別關(guān)系，它從給定的初值出發(fā)，通過(guò)這種關(guān)系一步一步地通過(guò)遞推獲得所需結(jié)果。并給出遞推法解題的一般過(guò)程。2．遞推法的解題步驟：

1）按次序研究集合中最初最原始的若干問(wèn)題。

2)按次序?qū)で蠹现袉?wèn)題間的轉(zhuǎn)換規(guī)律即遞推關(guān)系，使問(wèn)題逐次轉(zhuǎn)化成較低層級(jí)或簡(jiǎn)單的且能解決問(wèn)題的或已解決的問(wèn)題。二、遞推法在解題中的應(yīng)用

遞推法在解題中的應(yīng)用十分廣泛，遞推法的特征是化難為易、化繁為簡(jiǎn)。使用遞推法時(shí)，先考慮與題目有關(guān)系的另一個(gè)較為簡(jiǎn)單的問(wèn)題，并加以解決。然后以此為基礎(chǔ)，尋求規(guī)律，一步一步遞推出原題的解答。

1．有一段樓梯有10段臺(tái)階，規(guī)定每一步只能跨一級(jí)或兩級(jí)，問(wèn)：要登上第10級(jí)臺(tái)階有多

少種不同的走法？

解：跨到其次級(jí)臺(tái)階，可以每次跨一級(jí)，也可以一次跨二級(jí)，共有2種不同的走法。

第三級(jí)臺(tái)階，可以由第一級(jí)臺(tái)階跨二級(jí)臺(tái)階到達(dá)，也可以由其次級(jí)臺(tái)階跨一級(jí)到達(dá)。而到達(dá)第一級(jí)和其次級(jí)臺(tái)階各有1、2種不同的走法，所以到達(dá)第三級(jí)臺(tái)階共有1+2=3種不同的走法。以下類推

所以，登上第三階、第四階、?的不同走法次數(shù)依次為登上它的前兩個(gè)臺(tái)階走法數(shù)的和。即依次為1，2，3，5，8，13，21，34，55，89，?

所以登上第十級(jí)臺(tái)階共有89種不同的走法。這列數(shù)為斐波納次數(shù)列。用遞推關(guān)系求組合數(shù)排列數(shù)的方法步驟為：對(duì)相鄰組合數(shù)先建立某種遞推關(guān)系；再利用遞推關(guān)系求得所需要的結(jié)果。

2．同室4人各寫一張賀年卡，先集中起來(lái)，然后每人從中拿一張別人送出的賀年卡，則4

張賀年卡不同的拿法有（）

A6種B9種C11種D23種

解我們先把文中題目所涉及的問(wèn)題換一種說(shuō)法。即把1，2，3，4個(gè)數(shù)字排成一排，使得A不能排在第A位，A=1，2，3，4.求符合條件的排列數(shù)。

我們?cè)侔堰@問(wèn)題推廣為一般的模式。把1，2，3，?，n這n個(gè)數(shù)字排成一排，使得A不能排在第A位，A=1，2，3，?，n。求符合條件的排列數(shù)。

設(shè)n個(gè)數(shù)字的這種排列數(shù)為Bn，若能退出Bn的通項(xiàng)公式或遞推公式，那上面的問(wèn)題就可以解決了且能解決一些較為繁雜的問(wèn)題。利用遞推法的分析如下：

簡(jiǎn)單知道B1=0，B2=1，n≥3時(shí)，考慮1，2，3，?n這n個(gè)數(shù)字的所有符合條件的排列數(shù)（以下稱為n個(gè)元素的錯(cuò)位排列數(shù)）。我們根據(jù)在排列中的第一位的數(shù)字是2，3，?，n，而將這些排列分成n-1類，顯然每一類的排列數(shù)相等。那么有Bn=（n-1）bn（1）

考察在bn中的排列，它們都是2B2B3……Bn的形式，其中，Bj≠j，j=2，3，?，n.我們進(jìn)一步把這些排列分成兩類，稱為B2=1的為第一子類，并把其中的排列個(gè)數(shù)記為bn`;稱B2≠1的為其次子類，它的排列個(gè)數(shù)記為dn``,那么有bn=bn`+bn``(2)

在第一子類的排列具有21B3B4…..Bn的形式，Ij≠j，j=3，4，…..，n。所以bn`就是3，4，….，n，這n-2個(gè)元素的錯(cuò)位排列數(shù)Bn-2。在其次子類中的排列具有2B2B3….In的形式，其中I2≠1，j=3，4，…..，n。所以bn`就是1，3，4，……，n，這n-1個(gè)元素的錯(cuò)位排列數(shù)Bn-1因此得到bn=Bn-2+Bn-1（3）把（3）代入（1）得Bn=（n-1）（Bn-2+Bn-1）

于是我們得到遞推公式（4）Bn=（n-1）（Bn-2）B1=0，B2=1回到原題，利用遞推法公式（4），我們有B3=（3-1）

(B1+B2)=2×（0+1）=2B4=（4-1）

（B2+B3）=3×（1+2）=9故有9種方法。

顯然，遞推法具有一般性，利用遞推公式（4），我們還可以較易的解決一些常見(jiàn)的排列組合題。

例1.一個(gè)牧羊人趕著一群羊通過(guò)99個(gè)關(guān)口，每過(guò)一個(gè)關(guān)口，守關(guān)人將拿走當(dāng)時(shí)羊

的一半，然后退還一只，過(guò)完這些關(guān)口后牧羊人趕多少只羊？

分析：每到關(guān)口的守關(guān)人留羊的方法一致，即留下當(dāng)時(shí)羊的一半再退還一只，因而牧羊人剩下當(dāng)時(shí)羊的一半多一只。設(shè)過(guò)第n關(guān)后牧羊人剩下An+1只羊，則過(guò)第n關(guān)前的羊數(shù)為An只，由分析可建立數(shù)列的遞推關(guān)系試：An+1=+1.即：2An+1=An+2

由遞推關(guān)系可得：An=2（An+1-1）

將A100=2代入上式可得：A99=A98=…..=A1=2即為牧羊人原來(lái)羊的只數(shù)為2只。例2.用1，2，3，4，5組成如A1,A2,A3,A4,A5的五位數(shù)，但A1≠1,A2≠2,A3≠

3,A4≠4,A5≠5試求這樣的五位數(shù)的個(gè)數(shù)。

解：設(shè)這樣的五位數(shù)的個(gè)數(shù)為D5。由遞推公式（4）Dn=（n-1）（Dn-2+Dn-1）D1=0,D2=1得D3