有限棧的出棧序列計數(shù)問題分析

王文龍

(喀什師范學院信息工程技術系， 新疆喀什 844000)

有限棧的出棧序列計數(shù)問題分析

王文龍

(喀什師范學院信息工程技術系， 新疆喀什 844000)

出棧序列個數(shù)是棧研究的基本問題.目前的研究大都基于無限棧，即不考慮?？臻g的大小來討論出棧序列計數(shù)問題.但在現(xiàn)實應用中，棧大小往往是有限的，出棧序列問題就要復雜得多.從非降路徑計數(shù)的角度，分析了無限棧和有限棧的出棧序列計數(shù)問題；從二元函數(shù)的角度，給出了出棧序列計數(shù)的算法;最后設計出相應的程序進行實現(xiàn)和驗證.實驗證明，算法結果正確，算法設計易于理解.

有限棧；出棧序列；非降路徑

棧是限定僅在表尾端進行插入或刪除操作的特殊線性表.通常稱表尾端為棧頂，向棧中插入元素稱為進棧，從棧中刪除元素稱為出棧.由于插入和刪除運算僅在棧頂一端進行，因此棧具有后進先出的特性，這種特性使得棧有著十分廣泛的應用.對一個給定的入棧序列，文獻[1-9]對出棧序列的數(shù)量等問題進行了研究.然而，以上研究結果均基于無限棧的前提，即棧的大小是不受限制的，也就是棧的大小大于等于入棧序列的長度.而在某些情況下，棧的大小會受到限制，即棧的大小小于入棧序列的長度，此時有限棧的入棧出棧問題會變得較為復雜.因此，文中從非降路徑的角度，在棧大小不受限制和棧大小受限制兩種情況下，對出棧序列計數(shù)問題進行分析研究，并給出計算算法和實現(xiàn)程序.

為方便分析，將研究的有關棧的問題描述為：給定入棧序列(1,2,…,n)，求出棧序列數(shù)量.

1 棧大小不受限制情況下非降路徑的出棧序列計數(shù)

棧大小不受限制的出棧序列的計數(shù)，有多種方法[1-9],文中著重從非降路徑計數(shù)[10]的角度分析出棧序列的計數(shù)問題.

圖1 上三角計數(shù)Fig 1Count of upper triangular

不妨設棧長度為入棧序列長度n，此時所有出棧序列的計數(shù)，可以用非降路徑的計數(shù)解決.圖1中，若將上行一步看做入棧一個元素，將右行一步看做出棧一個元素，則所有出棧序列的計數(shù)等于上三角中從(0,0)到(n,n)的非降路徑總數(shù).

2 棧大小受限制情況下非降路徑的出棧序列計數(shù)

為方便后續(xù)計算，需要先做如下2個計數(shù).

2.1 計數(shù)1

圖2 直角梯形計數(shù)Fig 2Count of right angle trapezoid

2.2 計數(shù)2

考慮計算圖3由(0,0),(t,t),(s,t),(s-t,0)所組成的平行四邊形中，從(0,0)到(s,t)的非降路徑總數(shù).

圖3 平行四邊形計數(shù)Fig 3Count of paralleogram

因此，由(0,0),(t,t),(s,t),(s-t,0)組成的平行四邊形中，從(0,0)到(s,t)的非降路徑總數(shù)等于

即

2.3 棧大小受限制的出棧序列計數(shù)

當棧的大小為k，小于入棧序列長度n時，棧中元素不能超過k個，則出棧序列的計數(shù)對應于圖4上三角中從(0,0)到(n,n)不穿過y=x+k上點的非降路徑數(shù)，即圖4上三角中從(0,0)到(n,n)被y=x和y=x+k所夾的非降路徑總數(shù).

圖4 被y=x與y=x+k所夾的計數(shù)Fig 4Count between y=x and y=x+k

現(xiàn)需計算上三角中從(0,0)到(n,n)接觸(含穿過)y=x+k+1上點的非降路徑總數(shù).為求其值，結合非降路徑的特點，在圖5中，可以考慮求出接觸(含穿過)a1點的非降路徑總數(shù)、不接觸a1點而接觸(含穿過)b1點的非降路徑總數(shù)……依次類推,直到求出不接觸d1點之前的點而接觸(含穿過)d1點的非降路徑總數(shù)，然后將所求的非降路徑總數(shù)求和，即為上三角中從(0,0)到(n,n)接觸(含穿過)y=x+k+1上點的非降路徑總數(shù).

圖5 接觸y=x+k+1的計數(shù)Fig 5 Count of contact y=x+k+1

不接觸c1點之前點而接觸(含穿過)c1點的非降路徑總數(shù)為這兩部分之積

該式可化簡為

根據(jù)以上分析，上三角中從(0,0)到(n,n)被y=x和y=x+k所夾的非降路徑總數(shù)為

此值即為當棧的大小為k，小于入棧序列長度n時，出棧序列的計數(shù).

2.4 幾種特殊情況下的計數(shù)

2.3節(jié)中所得計數(shù)公式較為復雜，可以考慮以下幾種較特殊的情況下的計數(shù)問題.

圖的計數(shù)

則上三角中從(0,0)到(n,n)被y=x和y=x+k所夾的非降路徑總數(shù)為

此式可以化簡為

分析上式，當k=n-1時，值為

當k=n-2時，值為

2)當k=1時,不難發(fā)現(xiàn)出棧序列只有一種.

3)當k=2時,出棧序列的計數(shù)對應于圖7上三角中從(0,0)到(n,n)被y=x和y=x+2所夾的非降路徑總數(shù).

圖7 被y=x與y=x+2所夾的計數(shù)Fig 7Count between y=x and y=x+2

此時求非降路徑總數(shù)，可以做如下考慮.所求的非降路徑先由(0,0)到a，而后由a到b，再到c……直到e，最后由e到(n,n).由(0,0)到a只有1種選擇，而a到b有2種選擇，b到c有2種選擇……到e有2種選擇，e到(n,n)只有1種選擇.根據(jù)乘法法則可知，上三角中從(0,0)到(n,n)被y=x和y=x+2所夾的非降路徑總數(shù)等于2n-1，此即當k=2時，棧大小受限時的出棧序列的計數(shù).

3 計算算法及程序實現(xiàn)

為更好地計算出棧序列數(shù)量，從求二元函數(shù)值的角度，設計兩種情況下出棧序列計數(shù)的算法及改進算法，并給出相應的程序實現(xiàn).

3.1 棧大小不受限制

可以把問題描述為求一個二元函數(shù)f(x,y)的值，其中x表示待入棧元素個數(shù)，y表示已在棧中元素個數(shù).對棧的操作不外乎兩種：繼續(xù)入棧一個元素，則此時待入棧元素個數(shù)變?yōu)閤-1，棧中元素個數(shù)變?yōu)閥+1；出棧一個元素，則此時待入棧元素個數(shù)不變?yōu)閤，棧中元素個數(shù)變?yōu)閥-1.用函數(shù)表示為f(x,y)=f(x-1,y+1)+f(x,y-1).

再考慮x=0和y=0兩種特殊情況.當x=0時，則元素都在棧中，此時出棧序列數(shù)量為1，即f(0,y)=1；當y=0時，棧中無元素，此時只能入棧一個元素，待入棧元素個數(shù)為x-1，棧中元素個數(shù)為1，即f(x,0)=f(x-1,1).

此時，所求問題變?yōu)榍蠛瘮?shù)f(n,0)的值.根據(jù)以上分析，可采用遞歸函數(shù)解決計數(shù)問題.程序如下：

#include“iostream.h”

intstacknum(intx,inty)

{if(x==0)return1;

if(y==0)returnstacknum(x-1,1);

returnstacknum(x-1,y+1)+stacknum(x,y-1);}

void main()

{ intx,y;

cout<<“please inputxandy:”<

cin>>x>>y;

cout<

考慮到遞歸效率不高，可以對程序進行改進.用二維數(shù)組s[i][j]來記錄函數(shù)f(i,j)的值，則s[i][j]=s[i-1][j+1]+s[i][j-1].而當i=0時，s[0][j]=1;當j=0時，s[i][0]=s[i-1][1].由此可以得到如下效率更高的程序：

#include “iostream.h”

#defineN100

void inits(intx,ints[N][N])

{ inti,j;

for(i=0;i<=x;i++)

for(j=0;j<=x;j++)

{ if(i==0)s[i][j]=1; else if(j==0)s[i][j]=s[i-1][1];

else s[i][j]=s[i-1][j+1]+s[i][j-1];}}

void main()

{ intx,y,s[N][N]; cout<<“please inputxandy:”<

cin>>x>>y;

inits(x,s);

cout<

3.2 棧大小受限制

假設棧的大小為k，由3.1節(jié)可知，當y

可采用遞歸函數(shù)解決計數(shù)問題，程序如下：

#include “iostream.h”

intk;

long stacknum(intx,inty)

{ if((x==0)&&(y<=k)) return 1L;

if(y==0) return stacknum(x-1,1);

if(y==k) return stacknum(x,y-1); return stacknum(x-1,y+1)+stacknum(x,y-1);}

void main()

{ intn,m;

cout<< “please inputxyandk:”<

cin>>x>>y>>k;

cout<

亦可用二維數(shù)組記錄函數(shù)值，程序如下：

#include “iostream.h”

#defineN100

intk;

void inits(intx,int s[N][N])

{ inti,j;

for(i=0;i<=x;i++)

for(j=0;j<=k;j++)

{ if(i==0)s[i][j]=1; else if(j==0)s[i][j]=s[i-1][1]; else if(j==k)s[i][j]=s[i][j-1]; elses[i][j]=s[i-1][j+1]+s[i][j-1];}}

void main()

{ intx,y,s[N][N];

cout<<“please inputxyandk:”<

cin>>x>>y>>k;

inits(x,s); cout<

[1] 張先偉,曹雁鋒.用插入法解決堆棧輸出問題[J].計算機應用與軟件,2007,24(11):169-171.

[2] 唐銳.用后繼序列法解決堆棧輸出問題[J].小型微型計算機系統(tǒng),2006,27(12):2314-2316.

[3] 徐鳳生.出棧序列的性質及其求解新算法[J].計算機工程與應用,2006,42(5):66-68.

[4] 何坤金,陳正鳴,楊垠.基于算子的棧序列生成算法與實現(xiàn)[J].計算機工程與設計,2006,27(12):2266-2267.

[5] 唐保祥.棧序列及其生成算法[J].鄭州大學學報:自然科學版,2001,33(4):33-35.

[6] 李紅衛(wèi),徐亞平.出棧序列的研究[J].計算機技術與發(fā)展,2007,17(10):127-129.

[7] 袁紅娟.基于鏈表的出棧序列生成算法[J].河北北方學院學報:自然科學版,2006,22(5):71-75.

[8] 韓靜.“數(shù)據(jù)結構”課程中出棧序列的一種求解算法[J].計算機教育,2008,6(23):68-70.

[9] 吳集林.用二叉樹解決出棧序列問題[J].贛南師范學院學報:自然科學版,2005,26(6):28-30.

[10] 盧開澄,盧華明.組合數(shù)學[M].第4版.北京：清華大學出版社,2006:128-130.

(責任編輯 惠松騏)

Analysis of counting problems on limited stack-output

WANG Wen-long

(Department of Information Engineering and Technology,Kashgar Teachers College,Kashgar 844000,Xinjiang,China)

The stack-output number is a basic problem of stack research.The present research is mostly based on infinite stack,which does not consider the size of the stack,and the stack-output counts are discussed.But in the practical applications,the size of stack is often limited,the stack-output problem has much more complexity.From the perspective of the counting on not descend path,counting problem of limited stack and infinite stack on stack-output is analysed.And from the perspective of dual function,algorithms are designed.Finally the corresponding programs are designed and verified.The results show that the algorithm is correct,and the algorithm design is easy to understand.

stack;limited stack;stack-output;not descend path

2014-10-23;修改稿收到日期:2015-01-17

新疆自治區(qū)高?？蒲杏媱澲攸c項目(XJEDU2014I039)；喀什師范學院教研教改重點項目(KJDZ1303,KJDZ1202)；喀什師范學院重點課題((13)2456)

王文龍(1976—)，男，湖南雙峰人，副教授，碩士.主要研究方向為計算機軟件與信息安全. E-mail:wwl-yx@163.com

TP 311

A

1001-988Ⅹ(2015)04-0046-06