2013年腾讯笔试题:n个元素顺序入栈，出栈顺序有多少种？
2013年腾讯笔试题:n个元素顺序入栈，出栈顺序有多少种？
发布时间： 16:28:18
编辑：www.fx114.net
本篇文章主要介绍了"2013年腾讯笔试题:n个元素顺序入栈，出栈顺序有多少种？"，主要涉及到2013年腾讯笔试题:n个元素顺序入栈，出栈顺序有多少种？方面的内容，对于2013年腾讯笔试题:n个元素顺序入栈，出栈顺序有多少种？感兴趣的同学可以参考一下。
n个元素顺序入栈，出栈顺序有多少种？&&
转者注 这个的结果有数学公式的 是C(n,2n)-C(n-1,2n),至于公式怎么来,必须将问题转化为数学问题“卡塔兰数”(Catalan).程序员的做法是用递归,要想写出效率高的程序,就得用这个数学问题推导出来的
转载自 http:/blog/static//
第一次遇到这个题目，还是一年前在新东方的一次笔试中，那时还是一个填空题！我晕，我咋知道，好像课堂上没有见过，或许我学数据结构等课程时，根本就没有学透的原因吧！反正当时没有做出来。以下这两段程序都测试通过，代码是没有问题的，可以直接运行，若出错一般都是环境或配置造成。C版（网友提供）：在visual studio .net 2003上测试通过。
一、不得利用本站危害国家安全、泄露国家秘密，不得侵犯国家社会集体的和公民的合法权益，不得利用本站制作、复制和传播不法有害信息！
二、互相尊重，对自己的言论和行为负责。
本文标题：
本页链接：n个数有序地入栈，那么出栈的排列共有几种？。。_数学吧_百度贴吧
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&签到排名：今日本吧第个签到，本吧因你更精彩，明天继续来努力！
本吧签到人数：0成为超级会员，使用一键签到本月漏签0次！成为超级会员，赠送8张补签卡连续签到：天&&累计签到：天超级会员单次开通12个月以上，赠送连续签到卡3张
关注：419,704贴子：
n个数有序地入栈，那么出栈的排列共有几种？。。收藏
高中数学指导选「精锐」哈佛北大精英创立,骨干师资亲授,紧扣必考点,快速高效提分高中数学指导有限时间内做到高效复习尤为关键,提分及押题预测 专线400-883-8052
1应该栈是先入后出
不不不，我的意思是，一组数，比如1，2，3，4，……，n，按这个顺序入栈，但出栈的话可以有：1，2，3，4，……，n；n，……，3，2，1等等，只要满足后入先出条件的，共有几种
卡特兰数，证明留给楼主思考
想了几天没想出来
u哥哥回归了？
观音菩萨无处不在。。
来晚了，最近事情比较多，不好意思
高中数学_昂立中学生_汇集中学生培训教育师资,应试与能力双提升!快来立即预约吧,名额有限!热线:400-610-9188
来挖个坟。。不用一一对应和非降路径怎做。。
穷你妹啊递推式神马的有没有
度娘百科上不是有么、、
不准一一对应
不知道。。要不你把上面的人再依次召唤一遍吧。。
干啥..不是说了Catalan了么..证明的话不是直接就有递推式了么..
纠结的是不知道是卡特兰数时怎么给出递推式
按第一个进栈的元素出栈的时刻分类,sigma就有Catalan的递推公式了..
这个头像v5
登录百度帐号推荐应用
为兴趣而生，贴吧更懂你。或n个元素任意依次入栈出栈，共有几种出栈序列
正确答案应是:&&
-----------
即卡塔南数列~~~~
推导过程如下：
不同的出栈序列实际上对应着不同的入栈出栈操作，以1记为入栈，0记位出栈。
则问题实际上是求n个1和n个0构成的全排列，其中任意一个位置，它及它此前的数中，1个个数要大于等于0的个数。
n个1和n个0构成的全排列数为：
&& （2n）!
--------------
&& n! * n!
排除掉不符合要求的序列，即那些在某时刻出栈数大于入栈数的序列，即得结果。
不符合的序列数为：
&& （2n）！
----------------
&&(n+1)!(n-1)!
解释：求不符合要求的序列总数，用到了一个小技巧。在n个0和n个1构成的2n个数的序列中，假设第一次出现0的个数大于1个个数（即0的个数比1的个数大一）的位置为k，则k为奇数，k之前有相等数目的0和1，各为(k-1)/2.&&若把这k个数，0换成1，1换成0
，则原序列唯一对应上一个n＋1个1和n－1个0的序列。反之，任意一个由n＋1个1和n－1个0构成的序列也唯一的对应一个这样不合要求的序列。由于一一对应，故这样不合要求的序列数实际上等于有n＋1个1和n－1个0构成的排列数。（关于变换的一一对应，看官可自己琢磨，不再赘言）
故符合要求的数目是：
（2n）!&&&&&&&&&&&&&&&&
(2n)!&&&&&&&&&&&&&&&&&&&&&&
--------------&&－
------------------ = --------------------
n!&&&&&&&&&&&&&&&&(n+1)!(n-1)!&&&&&&&&&&
(n+1)!(n)!
已投稿到：
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。1376人阅读
算法（13）
1.基于栈的问题分析
我们把n个元素的出栈个数的记为f(n), 那么对于1,2,3, 我们很容易得出：
//即 12、21
//即 123、132、213、321、231
然后我们来考虑f(4), 我们给4个元素编号为a,b,c,d, 那么考虑：元素a只可能出现在1号位置，2号位置，3号位置和4号位置(很容易理解，一共就4个位置，比如abcd,元素a就在1号位置)。
1) 如果元素a在1号位置，那么只可能a进栈，马上出栈，此时还剩元素b、c、d等待操作，就是子问题f(3)；
2) 如果元素a在2号位置，那么一定有一个元素比a先出栈，即有f(1)种可能顺序（只能是b），还剩c、d，即f(2)，
根据乘法原理，一共的顺序个数为f(1) * f(2)；
3) 如果元素a在3号位置，那么一定有两个元素比1先出栈，即有f(2)种可能顺序（只能是b、c），还剩d，即f(1)， 根据乘法原理，一共的顺序个数为f(2) * f(1)；
4) 如果元素a在4号位置，那么一定是a先进栈，最后出栈，那么元素b、c、d的出栈顺序即是此小问题的解，即f(3)；
结合所有情况，即f(4) = f(3) + f(2) * f(1) + f(1) * f(2) + f(3);
为了规整化，我们定义f(0) = 1；于是f(4)可以重新写为：
f(4) = f(0)f(3) + f(1)*f(2) + f(2)
f(1) + f(3)*f(0)
然后我们推广到n，推广思路和n=4时完全一样，于是我们可以得到：
f(n) = f(0)*f(n-1) + f(1)*f(n-2) + … + f(n-1)*f(0)
但这只是一个递推公式（若编程实现，需要维护一个一维数组，时间复杂度为O(n^2)）。怎么把它转化为通项公式呢，复杂度仅为O(1)?
2. 相关的求解方法
（1）非常规数值分析
对于每一个数来说，必须进栈一次、出栈一次。我们把进栈设为状态‘1’，出栈设为状态‘0’。n个数的所有状态对应n个1和n个0组成的2n位二进制数。由于等待入栈的操作数按照1‥n的顺序排列、入栈的操作数b大于等于出栈的操作数a(a≤b)，因此输出序列的总数目=由左而右扫描由n个1和n个0组成的2n位二进制数，1的累计数不小于0的累计数的方案种数。
在2n位二进制数中填入n个1的方案数为c(2n,n),不填1的其余n位自动填0。从中减去不符合要求（由左而右扫描，0的累计数大于1的累计数）的方案数即为所求。
不符合要求的数的特征是由左而右扫描时，必然在某一奇数位2m+1位上首先出现m+1个0的累计数和m个1的累计数，此后的2(n-m)-1位上有n-m个 1和n-m-1个0。如若把后面这2(n-m)-1位上的0和1互换，使之成为n-m个0和n-m-1个1，结果得1个由n+1个0和n-1个1组成的2n位数，即一个不合要求的数对应于一个由n+1个0和n-1个1组成的排列。
反过来，任何一个由n+1个0和n-1个1组成的2n位二进制数，由于0的个数多2个，2n为偶数，故必在某一个奇数位上出现0的累计数超过1的累计数。同样在后面部分0和1互换，使之成为由n个0和n个1组成的2n位数，即n+1个0和n-1个1组成的2n位数必对应一个不符合要求的数。
因而不合要求的2n位数与n+1个0，n－1个1组成的排列一一对应。
显然，不符合要求的方案数为c(2n,n+1)。
由此得出输出序列的总数目=c(2n,n)-c(2n,n+1)=c(2n,n)/(n+1)。其中，n为节点的个数。
我们来看个例子:对于1 2 3这个入栈序列，1 1 0 1 0 0就是一个入栈出栈序列，第一个1代表元素1入栈，然后第二个1代表元素2入栈，然后第三个是0，代表出栈，即元素2出栈，然后第四个是1，代表元素3入栈，然后第五个是0，代表出栈，即元素3出栈，然后第六个是0，代表元素1出栈。最后1 1 0 1 0 0就代表了出栈序列2 3 1。
那么现在的问题就转换为如何求出所有符合条件的0 1序列了。其实这和以下问题相同:给定括号对数，输出所有符合要求的序列。如2对括号，输出有()()或者(())两种。1可以看成’(‘，0可以看成‘)’。
下面贴上本人的程序，并给出详细注释。
#include &iostream&
#include &vector&
using namespace std;
void func(vector&char&kind,int count[],int n)
if(count[0]&=1)
kind.push_back('(');
count[0]--;
func(kind,count,n);
count[0]++;
kind.pop_back();
if((count[1]&=1) && (count[1]&count[0]))
kind.push_back(')');
count[1]--;
func(kind,count,n);
count[1]++;
kind.pop_back();
if(kind.size()==2*n)
vector&char&::
for(iter=kind.begin();iter!=kind.end();iter++)
cout&&(*iter)&&" ";
int main()
cout && "please input the number of ():" &&
int count[2]={n-1,n};
vector&char&
kind.push_back('(');
func(kind,count,n);
count[0]存着左括号数目，count[1]存着右括号数目。一开始kind中压入左括号，因为第一个肯定是左括号。然后count数组初始化为n-1个左括号，n个右括号。然后我们递归的处理。如果剩余左括号数count[0]大于0，就可以把左括号压栈。而对于右括号，栈中左括号个数必须多于右括号个数，也就是剩余右括号个数大于左括号个数，即count[1]&count[0]时，才能将右括号压栈。如果栈中元素个数达到2n时，就把栈中元素输出。
下面贴出出栈序列代码，几乎和上面相同。
#include &iostream&
#include &stack&
#include &vector&
using namespace std;
int number=0;
void func(vector&int&kind,int count[],int n,int A[])
if(count[0]&=1)
kind.push_back(1);
count[0]--;
func(kind,count,n,A);
count[0]++;
kind.pop_back();
if((count[1]&=1) && (count[1]&count[0]))
kind.push_back(0);
count[1]--;
func(kind,count,n,A);
count[1]++;
kind.pop_back();
if(kind.size()==2*n)
vector&int&::
stack&int&
for(iter=kind.begin();iter!=kind.end();iter++)
if(1==(*iter))
stk.push(A[j]);
cout&&stk.top()&&" ";
stk.pop();
int main()
cout && "please input the number:" &&
cout && "please input the push sequence:" &&
for(i=0;i&n;i++)
cin&&A[i];
int count[2]={n-1,n};
vector&int&
kind.push_back(1);
cout&&"the result is:"&&
func(kind,count,n,A);
cout&&"total:"&&number&&
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：29670次
积分：1109
积分：1109
排名：千里之外
原创：79篇
转载：16篇
(5)(1)(10)(9)(6)(28)(38)}