進出棧算法分析(數(shù)學(xué)分析 代碼)

1、問題轉(zhuǎn)述：求一列共n輛的火車按順序通過一個棧所產(chǎn)生的排列總數(shù)。 分析：這一類組合計數(shù)題目顯然不能用搜索的方法把所有可能的移動方案都窮舉出來再統(tǒng)計總數(shù)這樣做時間復(fù)雜度極大。所以這道題應(yīng)當(dāng)根據(jù)問題本身的性質(zhì)，利用組合數(shù)學(xué)的原理，將原問題轉(zhuǎn)化為遞歸形式，找到計算總數(shù)的遞歸方程，再進行計算。  摘要： 算法一算法二算法三算法遞推遞推Catalan數(shù)時間復(fù)雜度O(n2)O(n2)O(n)空間復(fù)雜度O(n)O(n2)O(1)算法一：我們不妨直接設(shè)n輛火車產(chǎn)生的排列總數(shù)為f(n)?？纯茨懿荒苷业揭恍┮?guī)律。 如圖,n列火車通過棧,起始車頭在車列最前端。經(jīng)過移動

2、后,車頭處在了第a+1位,車頭前有a輛車,車頭后有b輛車(a>=0,b>=0)。則n=a+b+1,b=n-a-1。  若要達到上述移動目的,步驟為:(1)    將車頭進棧;(2)    將車頭后a輛車依次通過棧，移至軌道另一端；(3)    將車頭出棧，則車頭恰好排在第a+1位；(4)    將軌道右端剩余b輛車依次通過棧，移至軌道另一端；不難證明，移動方案僅此一種。問題是每個步驟又有許多種不同的移動方

3、法。顯然步驟（1）（3）各只有一種移動方法。仔細觀察步驟（2）（4）。我們前面定義了“n輛火車依次通過棧產(chǎn)生的排列總數(shù)為f(n)”，而步驟（2）恰恰是這個問題的子問題。即步驟二可寫為“將a輛火車依次通過?！?，根據(jù)前面定義，其移動方案總數(shù)為f(a)。同理，步驟(4)的移動方法總數(shù)為f(b)。根據(jù)乘法原理，要完成上述工作：總的方法數(shù)tot=步驟(1)的方法數(shù)*步驟(2)的方法數(shù)*步驟(3)的方法數(shù)*步驟(4)的方法數(shù)=1* f(a) * 1* f(b)=f(a) * f(b)=f(a) * f(n-a-1) 

4、 (因為b=n-a-1)我們目前已求得將n列火車通過棧，且將位于原車列首位的車頭經(jīng)過移動后位于移動后的車列第a+1位的方法總數(shù), 即f(a)*f(n-a-1)。但是原火車頭經(jīng)過移動后可能處在移動后車列的任意一個位置，即a的取值是任意的。由于共有n輛車，因此移動后原火車頭前面的車數(shù)可能有0n-1輛，即0an-1。要完成某個特定的移動方法，a只能取某個特定的值。根據(jù)加法原理，將n輛火車依次通過棧的移動總數(shù)為：總的方法數(shù) f(n) = 取a=0的方法數(shù) + 取a=1的方法數(shù) + . + 取a=n-1的方法數(shù)&#

5、160;               = f(0)*f(n-0-1) + f(1)*f(n-1-1) + f(2)*f(n-2-1) + + f(n-1)*f(n-(n-1)-1) f(0)=1;    有了以上遞歸公式，不難用遞推的方法寫出程序。算法一例程如下：#include<iostream>#include<cstring>using namespace std;l

6、ong f19;int n,i,j;int main()        while(cin>>n)              memset(f,0,sizeof(f);         f0=1;         for(i=1;i<

7、;=n;i+)          for(j=0;j<=i-1;j+)           fi+=fj*fi-j-1;         cout<<fn<<endl;            

8、;   算法二：前面所說的搜索法雖行不通，但它也許能給我們一些提示。如果用深度優(yōu)先搜索(DFS)，窮舉所有可能的移動方法來做的話，當(dāng)搜索到某個狀態(tài)下，所能做的移動方法無非有兩種：（1）將軌道右方的第一列火車進棧；（2）將棧頂?shù)幕疖嚦鰲＃M入左邊的軌道。設(shè)此時軌道右方，棧，軌道左方的火車數(shù)分別為a,b,c。我們就能用(a,b,c)表示出當(dāng)前的狀態(tài)。顯然n=a+b+c,則c=n-a-b。即已知a和b，c就被確定，所以我們可以用(a,b)來作為狀態(tài)的表示方法。則起始狀態(tài)為(n,0)，目標狀態(tài)為(0,0)。又由上面的兩種移動方法。我們可類似的得到兩種狀態(tài)轉(zhuǎn)移方式：

9、0;            進棧               (a-1,b+1)    (a>0)(a,b)              

10、0;                                       出棧          &#

11、160;  (a,b-1)      (b>0)再設(shè)f(a,b)為從狀態(tài)(a,b)通過移動火車變?yōu)闋顟B(tài)(0,0)的所有移動方法。類似于動態(tài)規(guī)劃的狀態(tài)轉(zhuǎn)移方程，我們可寫出以下遞歸式：f(a-1,b+1) + f(a,b-1)   (a>0,b>0)（a+bn）f(a,b) =     f(a-1,b+1)          

12、; (a>0,b=0)  (此時只能作進棧操作)f(a,b-1)              (a=0)       (此時只能作出棧操作)邊界值：f(0,0)=1。a+b<=n;按a的值從0n劃分階段，亦可通過遞推求得f(n,0)的值，即為所求。如果只保存兩個階段進行遞推，還可將空間復(fù)雜度降為O(n)。這個算法雖然不如算法一簡潔，但對于本題來說已

13、經(jīng)很不錯了。而且它在思維難度上要比算法一容易一些。算法二的例程如下：保存兩個階段進行遞推，空間復(fù)雜度降為O(n)。#include<iostream>#include<cstring>using namespace std;long f19;int n,a,b;int main()       while(cin>>n)              memset(f,0,sizeof

14、(f);         f0=1;        for(b=1;b<=n;b+)         fb=fb-1;        for(a=1;a<=n;a+)         for(b=0;b<

15、;=n-a;b+)                          fb=fb+1;               if(b>0)       

16、        fb+=fb-1;                      cout<<f0<<endl;                 &#

17、160;算法三：是不是動態(tài)規(guī)劃就是這道題的最優(yōu)算法呢？其實，本題還隱藏著更為精妙的數(shù)學(xué)思想：可以設(shè)入棧為1，出棧為0。n個數(shù)的所有狀態(tài)對應(yīng)n個1和n個0組成的2n位二進制數(shù)。由于等待入棧的操作數(shù)按照1.n的順序排列，入棧的操作數(shù)大于等于出棧的操作數(shù)，因此輸出序列的總數(shù)目等于由左而右掃描n個1和n個0組成的2n位二進制數(shù)，1的累計數(shù)不小于0的累計數(shù)方案種數(shù)。即為n的Catalan數(shù)。設(shè)P2n為這樣所得的數(shù)的個數(shù)。在2n位上填入n個1的方案數(shù)為：不填1的其余n位自動填以數(shù)0。從   中減去不符合要求的方案數(shù)即為所求。不合要求的數(shù)指的是從左而右掃描，出現(xiàn)0的累計數(shù)超過1

18、的累計數(shù)的數(shù)。     不合要求的數(shù)的特征是從左而右掃描時，必然在某一奇數(shù)2m+1位上首先出現(xiàn)m+1個0的累計數(shù)，和m個1的累計數(shù)。     此后的2（nm）1位上有nm個1，nm1個0。如若把后面這部分2（nm）1位，0與1交換，使之成為nm個0，nm1個1，結(jié)果得1個由n1個0和n1個1組成的2n位數(shù)，即一個不合要求的數(shù)對應(yīng)于一個由n1個0和n1個1組成的一個排列。     反過來，任何一個由n1個0，n1個1組成的2n位數(shù)，由于0的個數(shù)多2

19、個，2n是偶數(shù)，故必在某一個奇數(shù)位上出現(xiàn)0的累計數(shù)超過1的累計數(shù)。同樣在后面的部分，令0和1互換，使之成為由n個0和n個1組成的2n位數(shù)。即n1個0和n1個1組成的2n位數(shù)，必對應(yīng)于一個不合要求的數(shù)。     用上述方法建立了由n1個0和n1個1組成的2n位數(shù)，與由n個0和n個1組成的2n位數(shù)中從左向右掃描出現(xiàn)0的累計數(shù)超過1的累計數(shù)的數(shù)一一對應(yīng)。 其實，許多看似不相關(guān)的問題都和Catalan數(shù)有密切關(guān)系。例如所有節(jié)點數(shù)為n的二叉樹的個數(shù)就恰為上式中的P2n,另外設(shè)圓周上2n個點，用n條彼此在圓內(nèi)部無公共交點的弦連接這些點，共有P2n

20、種連接方式。在n×n的矩陣中，從(0,0)點走到(n,n)點，規(guī)定只能向下或向右走，且不能穿過左上到右下的對角線，共有P2n種走的方式。因此，Catalan數(shù)的應(yīng)用范圍很廣。/高精度計算Catalan數(shù)#include<iostream>#include<cstring>using namespace std;const int Max=50;int aMax;void Catalan(int n,int m)      int i,j,f=0,d=2,x;     fo

21、r(i=n-m+1;i<=n;i+)                for(f=0,j=0;j<=d;j+)                          x=aj*i+f;  

22、60;            f=x/10;               aj=x%10;                       wh

23、ile(aj=0)j-;           d=j+5;               for(i=m;i>=2;i-)                for(f=0,j=d;j>=0;j-)  &

24、#160;                       x=f*10+aj;               aj=x/i;           

25、;    f=x%i;                       j=d;while(aj=0) j-;          d=j+1;            

26、;     j=d;        while(aj=0)j-;     /*以下是計算Catalan數(shù)*/     d=j+1;     i=m+1;     for(f=0,j=d;j>=0;j-)                          x=f*10+aj;               aj=x/i; &