遞推關(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ù)組實現(xiàn)３．求遞推式的通項表達(dá)式：3．1、迭加法3．2、待定系數(shù)法

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

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

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

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

盤子。第三步：再借助1柱把2柱上的n-1個盤子移動到3上，所需的移動次

數(shù)為f(n-1)。由以上3步得出總共移動盤子的次數(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]表示四個柱子時，把i個盤子從原柱移動到目標(biāo)柱所需的最少移動次數(shù)。

j第一步：先把1柱上的前j個盤子移動到另外其中一個非目標(biāo)柱（2或3柱均可，假設(shè)移到2柱）上，此時3和4柱可以作為中間柱。移動次數(shù)為：f[j]。第二步：再把原1柱上剩下的i-j個盤子在3根柱子（1、3、4）之間移動，最后移動到目標(biāo)柱4上，因為此時2柱不能作為中間柱子使用，根據(jù)三柱問題可知，移動次數(shù)為：2^(i-j)-1。第三步：最后把非目標(biāo)柱2柱上的j個盤子移動到目標(biāo)柱上，次數(shù)為：f[j]。第八頁，共三十七頁，2022年，8月28日通過以上步驟我們可以初步得出：f[i]=2*f[j]+2^(i-j)-1j可取的范圍是1<=j<I，所以對于不同的j，得到的f[i]可能是不同的，本題要求最少的移動次數(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個盤子的最少移動次數(shù)F3[n]=2^n-1;F4[n]為Hanoi塔中4根柱子，n個盤子的最少移動次數(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個盤子時移動的最少次數(shù)：1、先把1柱上的前j個盤子移動到另外其中一個除m柱以外的非目標(biāo)柱上，移動次數(shù)為：f[m,j]；2、再把原1柱上剩下的n-j個盤子在m-1根柱子之間移動，最后移動到目標(biāo)柱m上，移動次數(shù)為：f[m-1,n-j]；3、最后把非目標(biāo)柱上的j個盤子移動到目標(biāo)柱沒柱上，移動次數(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條封閉曲線畫在平面上，而任何兩條封閉曲線恰好相交于兩點，且任何三條封閉曲線不相交于同一點，求這些封閉曲線把平面分割成的區(qū)域個數(shù)?！締栴}分析】：設(shè)f(n)為n條封閉曲線把平面分割成的區(qū)域個數(shù)。由圖4很容易得出：f(1)=2；f(2)=4。第十三頁，共三十七頁，2022年，8月28日假設(shè)當(dāng)前平面上已有的n-1條曲線將平面分割成f(n-1)-個區(qū)域，現(xiàn)在加入第n條封閉曲線。第n條曲線每與已有的n-1條曲線相交共有2(n-1)個交點，也就是說第n條曲線被前n-1條曲線分割成2(n-1)段弧線，而每一條弧線就會把原來的區(qū)域一分為二，即增加一個區(qū)域，所以共增加2(n-1)個區(qū)域F（n）=f（n-1）+2(n-1)第十四頁，共三十七頁，2022年，8月28日問題Ⅱ問題的提出：一個‘z’形曲線可以把一個平面分割成2部分。如圖所示。求n個‘z’形曲線最多能把平面分割成多少部分。寫出遞推式f(n)。【問題分析】：根據(jù)上圖容易得出：f（1）=2；f（2）=12。假設(shè)平面上已有n-1個‘z’圖形把平面分成了f（n-1）個區(qū)域。加入第n個‘z’后，單獨考慮第n個‘z’的3條邊，每一條邊和前面的n-1個‘z’共有3（n-1）個交點，即這條邊被分成3（n-1）+1部分，所以增加3（n-1）+1個區(qū)域，3條邊共增加3（3（n-1）+1）個區(qū)域。但是第n個‘z’本身有2個交點，故少了2個區(qū)域，所以實際增加了3（3（n-1）+1）-2個區(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個上述圖形可以將平面劃分的區(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邊形的三角形剖分在一個凸n邊形中，通過不相交于n邊形內(nèi)部的對角線，把n邊形拆分成若干三角形，不同的拆分?jǐn)?shù)目用f(n)表之，f(n)即為Catalan數(shù)。例如五邊形有如下五種拆分方案，故f(5)=5。求對于一個任意的凸n邊形相應(yīng)的f(n)。第十七頁，共三十七頁，2022年，8月28日區(qū)域①是一個凸k邊形，區(qū)域②是一個凸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個結(jié)點能構(gòu)成不同二叉數(shù)的數(shù)目?！締栴}分析】：設(shè)F(n)為n個結(jié)點組成二叉樹的數(shù)目。容易知道：f(1)=1;f(2)=2,f(3)=5選定1個結(jié)點為根，左子樹結(jié)點的個數(shù)為i，二叉樹數(shù)目f（i）種；右子樹結(jié)點數(shù)目為n-i-1，二叉樹數(shù)目f（n-i-1）種，I的可取范圍[0，n-1]。所以有：F(n)=

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

設(shè)有n個不同的球，分別用b1,b2,……bn表示。從中取出一個球bn，bn的放法有以下兩種：bn獨自占一個盒子；那么剩下的球只能放在m-1個盒子中，方案數(shù)為S(n-1,m-1)bn與別的球共占一個盒子；那么可以事先將b1,b2,……bn-1這n-1個球放入m個盒子中，然后再將球bn可以放入其中一個盒子中，方案數(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是一個包含n個元素的集合，S={b1,b2,b3,…,bn},現(xiàn)需要將S集合劃分為m個滿足如下條件的集合S1,S2,…Sm。Si≠∮;Si∩Sj=∮;

S1∪S2∪…∪Sm=S;(1<=I,j<=m)則稱S1,S2,…,Sm是S的一個劃分。編程：輸入n和m的值，輸出不同的劃分方案數(shù)。要求：輸入數(shù)據(jù)有一行，第一個數(shù)是n,第二個數(shù)m。樣例：輸入：43輸出：6不同的方案數(shù)用S(n,m)表示從中取出bn，bn的放法有以下兩種：１、bn獨自占一個集合；那么剩下的數(shù)只能放在m-1個集合中，方案數(shù)為；２、bn與別的數(shù)共占一個集合；那么我們可以先將b1,b2,……bn-1這n-1個數(shù)劃分為m個集合，然后再將bn可以任意放入其中一個集合中，方案數(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}中能夠選擇的沒有兩個連續(xù)整數(shù)的k個元素子集的數(shù)目，求遞歸式f(n,k)?！締栴}分析】：N有兩種情況：①當(dāng)n在子集時，則n-1一定不在子集中，即在{1，2，。。。，n-2}中選k-1個元素，數(shù)目為f(n-2,k-1)。②當(dāng)n不在子集中時，則在{1，2，。。。，n-1}中選k個元素，數(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)

輸出：一個整數(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個1分到每一份，然后再把剩下的I-j分成j份即可，分法有：f(I-j,j).第二類:j份中至少有一份為1的分法，可以先那出一個1作為單獨的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ù)組實現(xiàn)３．求遞推式的通項表達(dá)式：3．1、迭加法3．2、待定系數(shù)法3．3、特征方程法3．4、生成函數(shù)法遞推式的求解方法：第二十五頁，共三十七頁，2022年，8月28日1、遞歸函數(shù)用遞歸函數(shù)來實現(xiàn)遞推式是初學(xué)選手們采用最多的求解方法，只要設(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ù)組實現(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求遞推式的通項表達(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個等式相加得到：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的通項。令: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)的通項第三十頁，共三十七頁，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個互不相同的解X1,X2,…..Xk，則通解為：F(n)=c1X1n+c2X2n+…….+ckXknc1,c2……ck待定。第三十一頁