出栈序列统计解题报告

出栈序列统计解题报告

ID:38336423

大小:24.00 KB

页数:3页

时间:2019-06-10

出栈序列统计解题报告_第1页
出栈序列统计解题报告_第2页
出栈序列统计解题报告_第3页
资源描述:

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

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.

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。