遞推關(guān)系的建立及其求解方法

遞推關(guān)系的建立及其求解方法第一頁，共三十七頁，2022年，8月28日一、遞推式的建立1、Hanoi塔問題問題Ⅰ:三柱問題問題Ⅱ：四柱問題問題Ⅲ：m柱問題2、平面分割問題問題Ⅰ：封閉曲線分割平面問題Ⅱ：‘Z’分割平面問題Ⅲ：‘M’分割平面3、Catalan數(shù)問題一：凸n邊形的三角形剖分問題二：二叉樹數(shù)目問題三：出棧序列4、第二類Stirling數(shù)問題一：放置小球問題二：集合劃分問題5、其他問題一：集合取數(shù)問題問題二：整數(shù)劃分問題二、遞推式的求解方法：1．遞歸函數(shù)２．用數(shù)組實(shí)現(xiàn)３．求遞推式的通項(xiàng)表達(dá)式：3．1、迭加法3．2、待定系數(shù)法

3．3、特征方程法3．4、生成函數(shù)法第二頁，共三十七頁，2022年，8月28日一、遞推式的建立1、Hanoi塔問題問題的提出：Hanoi塔由n個(gè)大小不同的圓盤和m根木柱1,2,3…….m組成。開始時(shí)，這n個(gè)圓盤由大到小依次套在1柱上，如圖所示。

現(xiàn)在要求把1柱上n個(gè)圓盤按下述規(guī)則移到m柱上：(1)一次只能移一個(gè)圓盤；(2)圓盤只能在m個(gè)柱上存放；(3)在移動(dòng)過程中，不允許大盤壓小盤。求將這n個(gè)盤子從1柱移動(dòng)到m柱上所需要移動(dòng)盤子的最少次數(shù)。第三頁，共三十七頁，2022年，8月28日問題Ⅰ:三柱問題設(shè)f(n)為n個(gè)盤子從1柱移到3柱所需移動(dòng)的最少盤次。

當(dāng)n=1時(shí)，f(1)=1。當(dāng)n=2時(shí)，f(2)=3。第四頁，共三十七頁，2022年，8月28日以此類推，當(dāng)1柱上有n(n>2)個(gè)盤子時(shí)，我們可以利用下列步驟：第一步：先借助3柱把1柱上面的n-1個(gè)盤子移動(dòng)到2柱上，所需的移

動(dòng)次數(shù)為f(n-1)。第二步：然后再把1柱最下面的一個(gè)盤子移動(dòng)到3柱上，只需要1次

盤子。第三步：再借助1柱把2柱上的n-1個(gè)盤子移動(dòng)到3上，所需的移動(dòng)次

數(shù)為f(n-1)。由以上3步得出總共移動(dòng)盤子的次數(shù)為：f(n-1)+1+f(n-1)。所以：f(n)=2f(n-1)+1f(n)=2n-1第五頁，共三十七頁，2022年，8月28日問題Ⅱ：四柱問題第六頁，共三十七頁，2022年，8月28日第七頁，共三十七頁，2022年，8月28日【問題分析】：令f[i]表示四個(gè)柱子時(shí)，把i個(gè)盤子從原柱移動(dòng)到目標(biāo)柱所需的最少移動(dòng)次數(shù)。

j第一步：先把1柱上的前j個(gè)盤子移動(dòng)到另外其中一個(gè)非目標(biāo)柱（2或3柱均可，假設(shè)移到2柱）上，此時(shí)3和4柱可以作為中間柱。移動(dòng)次數(shù)為：f[j]。第二步：再把原1柱上剩下的i-j個(gè)盤子在3根柱子（1、3、4）之間移動(dòng)，最后移動(dòng)到目標(biāo)柱4上，因?yàn)榇藭r(shí)2柱不能作為中間柱子使用，根據(jù)三柱問題可知，移動(dòng)次數(shù)為：2^(i-j)-1。第三步：最后把非目標(biāo)柱2柱上的j個(gè)盤子移動(dòng)到目標(biāo)柱上，次數(shù)為：f[j]。第八頁，共三十七頁，2022年，8月28日通過以上步驟我們可以初步得出：f[i]=2*f[j]+2^(i-j)-1j可取的范圍是1<=j<I，所以對于不同的j，得到的f[i]可能是不同的，本題要求最少的移動(dòng)次數(shù)f[i]=min{2*f[j]+2^(i-j)-1}，其中1<=j<I第九頁，共三十七頁，2022年，8月28日constMaxNum=1000;varn:integer;F3,F4:array[1..MaxNum]ofdouble;procedureInit;vari:integer;beginfillChar(F3,sizeOf(F3),0);fillChar(F4,sizeOf(F4),0);readln(n);F3[1]:=1;F4[1]:=1;{*F3[n]為Hanoi塔中3根柱子，n個(gè)盤子的最少移動(dòng)次數(shù)F3[n]=2^n-1;F4[n]為Hanoi塔中4根柱子，n個(gè)盤子的最少移動(dòng)次數(shù)*}

fori:=2tondoF3[i]:=2*F3[i-1]+1;end;

第十頁，共三十七頁，2022年，8月28日procedureRun;vari,j:integer;minF4i,temp:double;beginfori:=2tondobeginminF4i:=1e+100;forj:=1toi-1dobegintemp:=2*F4[j]+F3[i-j];if(temp<minF4i)thenminF4i:=temp;end;{*F4[i]=min(2*F4[j]+F3[i-j]);(1=<j<=i-1)*}F4[i]:=minF4i;end;writeln(F4[n]:0:0);end;beginInit;Run;end.第十一頁，共三十七頁，2022年，8月28日問題Ⅲ：m柱問題【問題分析】：設(shè)F(m,n)為m根柱子,n個(gè)盤子時(shí)移動(dòng)的最少次數(shù)：1、先把1柱上的前j個(gè)盤子移動(dòng)到另外其中一個(gè)除m柱以外的非目標(biāo)柱上，移動(dòng)次數(shù)為：f[m,j]；2、再把原1柱上剩下的n-j個(gè)盤子在m-1根柱子之間移動(dòng)，最后移動(dòng)到目標(biāo)柱m上，移動(dòng)次數(shù)為：f[m-1,n-j]；3、最后把非目標(biāo)柱上的j個(gè)盤子移動(dòng)到目標(biāo)柱沒柱上，移動(dòng)次數(shù)為：f[m,j]。F(m,n)=min{2*F(m,j)+F(m-1,n-j)}

(1<=j<n)j第十二頁，共三十七頁，2022年，8月28日2、平面分割問題問題Ⅰ問題的提出：設(shè)有n條封閉曲線畫在平面上，而任何兩條封閉曲線恰好相交于兩點(diǎn)，且任何三條封閉曲線不相交于同一點(diǎn)，求這些封閉曲線把平面分割成的區(qū)域個(gè)數(shù)?！締栴}分析】：設(shè)f(n)為n條封閉曲線把平面分割成的區(qū)域個(gè)數(shù)。由圖4很容易得出：f(1)=2；f(2)=4。第十三頁，共三十七頁，2022年，8月28日假設(shè)當(dāng)前平面上已有的n-1條曲線將平面分割成f(n-1)-個(gè)區(qū)域，現(xiàn)在加入第n條封閉曲線。第n條曲線每與已有的n-1條曲線相交共有2(n-1)個(gè)交點(diǎn)，也就是說第n條曲線被前n-1條曲線分割成2(n-1)段弧線，而每一條弧線就會(huì)把原來的區(qū)域一分為二，即增加一個(gè)區(qū)域，所以共增加2(n-1)個(gè)區(qū)域F（n）=f（n-1）+2(n-1)第十四頁，共三十七頁，2022年，8月28日問題Ⅱ問題的提出：一個(gè)‘z’形曲線可以把一個(gè)平面分割成2部分。如圖所示。求n個(gè)‘z’形曲線最多能把平面分割成多少部分。寫出遞推式f(n)?！締栴}分析】：根據(jù)上圖容易得出：f（1）=2；f（2）=12。假設(shè)平面上已有n-1個(gè)‘z’圖形把平面分成了f（n-1）個(gè)區(qū)域。加入第n個(gè)‘z’后，單獨(dú)考慮第n個(gè)‘z’的3條邊，每一條邊和前面的n-1個(gè)‘z’共有3（n-1）個(gè)交點(diǎn)，即這條邊被分成3（n-1）+1部分，所以增加3（n-1）+1個(gè)區(qū)域，3條邊共增加3（3（n-1）+1）個(gè)區(qū)域。但是第n個(gè)‘z’本身有2個(gè)交點(diǎn)，故少了2個(gè)區(qū)域，所以實(shí)際增加了3（3（n-1）+1）-2個(gè)區(qū)域。由以上得出：f（n）=f（n-1）+3（3（n-1）+1）-2即：f（n）=f（n-1）+9n-8初始條件：f（1）=2第十五頁，共三十七頁，2022年，8月28日問題Ⅲ：‘M’分割平面問題二的擴(kuò)展：在問題二的基礎(chǔ)上進(jìn)一步考慮：如果‘z’圖形擴(kuò)展為m邊的下列圖形：看一下問題的解。通過上面的分析我們很容易知道：n個(gè)上述圖形可以將平面劃分的區(qū)域的遞推關(guān)系：f（n）=f（n-1）+m（m（n-1）+1）-（m-1）初始條件：f（1）=2第十六頁，共三十七頁，2022年，8月28日3、Catalan數(shù)問題一：凸n邊形的三角形剖分在一個(gè)凸n邊形中，通過不相交于n邊形內(nèi)部的對角線，把n邊形拆分成若干三角形，不同的拆分?jǐn)?shù)目用f(n)表之，f(n)即為Catalan數(shù)。例如五邊形有如下五種拆分方案，故f(5)=5。求對于一個(gè)任意的凸n邊形相應(yīng)的f(n)。第十七頁，共三十七頁，2022年，8月28日區(qū)域①是一個(gè)凸k邊形，區(qū)域②是一個(gè)凸n-k+1邊形，區(qū)域①的拆分方案總數(shù)是f(k)區(qū)域②的拆分方案數(shù)為f(n-k+1)，故包含△P1PkPn的n邊形的拆分方案數(shù)為f(k)*f(n-k+1)種F(n)=第十八頁，共三十七頁，2022年，8月28日問題二：二叉樹數(shù)目問題描述：求n個(gè)結(jié)點(diǎn)能構(gòu)成不同二叉數(shù)的數(shù)目?！締栴}分析】：設(shè)F(n)為n個(gè)結(jié)點(diǎn)組成二叉樹的數(shù)目。容易知道：f(1)=1;f(2)=2,f(3)=5選定1個(gè)結(jié)點(diǎn)為根，左子樹結(jié)點(diǎn)的個(gè)數(shù)為i，二叉樹數(shù)目f（i）種；右子樹結(jié)點(diǎn)數(shù)目為n-i-1，二叉樹數(shù)目f（n-i-1）種，I的可取范圍[0，n-1]。所以有：F(n)=

為了計(jì)算的方便：約定f（0）=1第十九頁，共三十七頁，2022年，8月28日問題三：出棧序列問題描述：N個(gè)不同元素按一定的順序入棧，求不同的出棧序列數(shù)目?！締栴}分析】：設(shè)f（n）為n個(gè)元素的不同出棧序列數(shù)目。容易得出：f（1）=1；f（2）=2。第n個(gè)元素可以第i（1<=i<=n）個(gè)出棧，前面已出棧有i-1個(gè)元素，出棧方法：f（i-1）；后面出棧n-I個(gè)元素，出棧方法為：f（n-i）。所以有：F(n)=約定：F(0)=1F(n)=第二十頁，共三十七頁，2022年，8月28日4、第二類Stirling數(shù)問題一：放置小球n個(gè)有區(qū)別的球放到m個(gè)相同的盒子中，要求無一空盒，其不同的方案數(shù)用S(n,m)表示，稱為第二類Stirling數(shù)

設(shè)有n個(gè)不同的球，分別用b1,b2,……bn表示。從中取出一個(gè)球bn，bn的放法有以下兩種：bn獨(dú)自占一個(gè)盒子；那么剩下的球只能放在m-1個(gè)盒子中，方案數(shù)為S(n-1,m-1)bn與別的球共占一個(gè)盒子；那么可以事先將b1,b2,……bn-1這n-1個(gè)球放入m個(gè)盒子中，然后再將球bn可以放入其中一個(gè)盒子中，方案數(shù)為mS(n-1,m)S(n,m)=mS(n-1,m)+S(n-1,m-1)(n>1,m1)第二十一頁，共三十七頁，2022年，8月28日問題二：集合劃分問題。設(shè)S是一個(gè)包含n個(gè)元素的集合，S={b1,b2,b3,…,bn},現(xiàn)需要將S集合劃分為m個(gè)滿足如下條件的集合S1,S2,…Sm。Si≠∮;Si∩Sj=∮;

S1∪S2∪…∪Sm=S;(1<=I,j<=m)則稱S1,S2,…,Sm是S的一個(gè)劃分。編程：輸入n和m的值，輸出不同的劃分方案數(shù)。要求：輸入數(shù)據(jù)有一行，第一個(gè)數(shù)是n,第二個(gè)數(shù)m。樣例：輸入：43輸出：6不同的方案數(shù)用S(n,m)表示從中取出bn，bn的放法有以下兩種：１、bn獨(dú)自占一個(gè)集合；那么剩下的數(shù)只能放在m-1個(gè)集合中，方案數(shù)為；２、bn與別的數(shù)共占一個(gè)集合；那么我們可以先將b1,b2,……bn-1這n-1個(gè)數(shù)劃分為m個(gè)集合，然后再將bn可以任意放入其中一個(gè)集合中，方案數(shù)為綜合以上兩種情況可以得出：S(n-1,m-1)m*S(n-1,m)S(n,m)=m*S(n-1,m)+S(n-1,m-1)(n>1,m1)邊界條件：S2(n,1)=1；S2(n,n)=1；S2(n,k)=0(k>n)。第二十二頁，共三十七頁，2022年，8月28日5、其他：１）‘集合取數(shù)問題設(shè)f(n,k)是從集合{1，2，。。。，n}中能夠選擇的沒有兩個(gè)連續(xù)整數(shù)的k個(gè)元素子集的數(shù)目，求遞歸式f(n,k)?！締栴}分析】：N有兩種情況：①當(dāng)n在子集時(shí)，則n-1一定不在子集中，即在{1，2，。。。，n-2}中選k-1個(gè)元素，數(shù)目為f(n-2,k-1)。②當(dāng)n不在子集中時(shí)，則在{1，2，。。。，n-1}中選k個(gè)元素，數(shù)目為f(n-1,k)。所以：f(n,k)=f(n-2,k-1)+f(n-1,k)邊界條件：F(n,1)=n,f(n,k)=0(n<=k)第二十三頁，共三十七頁，2022年，8月28日２）整數(shù)劃分問題將整數(shù)n分成k份，且每份不能為空，任意兩種分法不能相同(不考慮順序)。

例如：n=7，k=3，下面三種分法被認(rèn)為是相同的。

1，1，5;1，5，1;5，1，1;

問有多少種不同的分法。

輸入：n，k(6<n<=200，2<=k<=6)

輸出：一個(gè)整數(shù)，即不同的分法。樣例

輸入：73

輸出：4{四種分法為：1，1，5;1，2，4;1，3，3;2，2，3;}【問題分析】：用f(I,j)表示將整數(shù)I分成j分的分法，可以劃分為兩類：第一類：j分中不包含1的分法，為保證每份都>=2，可以先那出j個(gè)1分到每一份，然后再把剩下的I-j分成j份即可，分法有：f(I-j,j).第二類:j份中至少有一份為1的分法，可以先那出一個(gè)1作為單獨(dú)的1份，剩下的I-1再分成j-1份即可，分法有：f(I-1,j-1).所以：f(I,j)=f(I-j,j)+f(I-1,j-1)邊界條件：f（i，1）=1，f（i，j）=0，（I<j）第二十四頁，共三十七頁，2022年，8月28日1．遞歸函數(shù)２．用數(shù)組實(shí)現(xiàn)３．求遞推式的通項(xiàng)表達(dá)式：3．1、迭加法3．2、待定系數(shù)法3．3、特征方程法3．4、生成函數(shù)法遞推式的求解方法：第二十五頁，共三十七頁，2022年，8月28日1、遞歸函數(shù)用遞歸函數(shù)來實(shí)現(xiàn)遞推式是初學(xué)選手們采用最多的求解方法，只要設(shè)置正確的邊界條件，相對來說比較容易實(shí)現(xiàn)。如：集合取數(shù)問題f(n,k)=f(n-2,k-1)+f(n-1,k)邊界條件：F(n,1)=n,f(n,k)=0(n<=k)functionf(n,k:integer):integer;beginifk=1thenf:=nelseifn<=kthenf:=0elsef:=f(n-2,k-1)+f(n-1,k);end;第二十六頁，共三十七頁，2022年，8月28日2用數(shù)組實(shí)現(xiàn)集合劃分問題:S(n,m)=m*S(n-1,m)+S(n-1,m-1)(n>1,m1)邊界條件：S2(n,1)=1；S2(n,n)=1；S2(n,k)=0(k>n)。vars:array[1..100,1..100]oflongint;n,m,i,j:integer;beginread(n,m);fillchar(s,sizeof(s),0);

fori:=1tondos[i,1]:=1;fori:=1tomdos[i,i]:=1;fori:=2tomdoforj:=itondos[j,i]:=i*s[j-1,i]+s[j-1,i-1];

writeln(s[n,m]);end.第二十七頁，共三十七頁，2022年，8月28日3求遞推式的通項(xiàng)表達(dá)式3．1、迭加法一般符合下列形式的遞推式可以使用迭代法。F(n)=f(n-1)+g(n)其中：g(n)是關(guān)于n的線性表達(dá)式。F(2)=f(1)+9*2-8F(3)=f(2)+9*3-8F(4)=f(3)+9*4-8┆┆F(n)=f(n-1)+9*n-8以上n-1個(gè)等式相加得到：f(n)=f(1)+9*(2+3+4+……+n)-8*(n-1)即：f(n)=9*n*n/2-7*n/2+1如：平面分割問題二:f（n）=f（n-1）+9n-8初始條件：f（1）=2第二十八頁，共三十七頁，2022年，8月28日3．2、待定系數(shù)法適合下列格式的遞推式：F(n)=a*f(n-1)+g(n)a>1例1：Hanoi塔三柱問題：f(n)=2f(n-1)+1，邊界條件：f(1)=1令：f(n)+A=2(f(n-1)+A)A為待定系數(shù)求得A=1,即：f(n)+1=2(f(n-1)+1)由等比數(shù)列性質(zhì)得出：f(n)+1＝2n-1(f(1)+1)=2n所以：f(n)＝2n－1第二十九頁，共三十七頁，2022年，8月28日例2：求f(n)=3f(n-1)+n2+n+2的通項(xiàng)。令:f(n)+An2+Bn+c=3(f(n-1)+A(n-1)2+B(n-1)+c)A，B，C為待定系數(shù)。由于上述恒等成立，得：2A=12B-6A=03+3B+2C=0求出：A,B,C后，從而得出f(n)的通項(xiàng)第三十頁，共三十七頁，2022年，8月28日3．3、特征方程法如果a1,,……ak是常數(shù)，且ak<>=0,n>k，則遞推關(guān)系

F(n)=a1f(n-1)+a2f(n-2)+……akf(n-k)稱為k階常系數(shù)線性齊次遞推關(guān)系。它的特征方程是：Xk-a1Xk-1-a2Xk-2-……-ak=0只要求出特征方程的根，再由初始條件表達(dá)式中的待定系數(shù)，便可以得到原遞推關(guān)系的解。如果特征方程有k個(gè)互不相同的解X1,X2,…..Xk，則通解為：F(n)=c1X1n+c2X2n+…….+ckXknc1,c2……ck待定。第三十一頁