出栈序列统计解题报告

《出栈序列统计解题报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、出栈序列统计解题报告题目描述很简单，将数据通过栈输的序列数目输出。由于只有两种操作push和pop（即入栈和出栈），所以我们可以把入栈操作记为0，出栈操作记为1。所以这道题可以转化为在2n个数中放入n个1（其余的填充0）且满足任何一个位置中的1个数不大于0的个数的排列方式。有了这样一个模型解题就有了我们的方向。1、直接接受的方法应推搜索：我们可以枚举所有满足要求的排列方式，再不重复的前提下将计数器加1。方法很简单但是效率很低很低。2、O(n)的算法（组合法）：首先不要过于激动我们的两种算法的效率差距。经过下面分析你

2、会发现其实我们所要求的只不过是卡特兰数。首先在2n个位置中放n个1的方法有C（n/2n）种，当然其中也有不满足情况的序列。那么不满足情况的序列有什么性质呢？再不满足要求的序列中肯定有一个地方满足“1的个数”=“0的个数”+1，此时这个位置以后的1个数为0的个数-1（因为他们个数均各为n）。我们不妨把此位置以左的0和1对调（即原为1出改为0，原为0处改为1），则肯定有n+1个0和n-1个1，所以C(n-1/2n)种可能他不满足我们的要求。因此所求的数为C(n/2n)-C(n-1/2n),经过数学化简我们可以发现该式是

3、等价于C(n/2n)/（n+1），即为卡特兰数。以该模型为基础的实际问题有非常多，例如球票问题……另外由于数字较大，所以需要高精度算法。附程序据参考：programstack;varc:array[1..10000]oflongint;n,i,j,k,t,z:longint;beginassign(input,'stack.in');reset(input);assign(output,'stack.out');rewrite(output);readln(n);fillchar(c,sizeof(c),0);c[

4、1]:=1;z:=1;fori:=2*ndownton+2dobeginforj:=1tozdoc[j]:=c[j]*i;forj:=1toz+4dobeginc[j+1]:=c[j+1]+c[j]div10;c[j]:=c[j]mod10;end;z:=z+5;whilec[z]=0dodec(z);end;fori:=ndownto2dobegint:=0;forj:=zdownto1dobegink:=c[j];c[j]:=(k+t*10)divi;t:=(k+t*10)modi;end;whilec[z]=

5、0dodec(z);end;fori:=zdownto1dowrite(c[i]);writeln;close(input);close(output);end.