16:10 提问
整形数字元素1，2，3依次进栈，有几种出栈顺序？
3个整形数字元素1，2，3依次进栈，请问有几种出栈顺序？
老师说答案是5.
为什么啊，不是6吗？
按赞数排序
（1）3个均入栈后才可出栈
1(in)、2(in)、3(in)、3(out)、2(0ut)、1(out)
（2）2个先入栈后才可以出栈
1(in)、2(in)、2(0ut)、1(out)、3(in)、3(out)
1(in)、2(in)、2(0ut)、3(in)、3(out)、1(out)
（3）1个先入栈后才可出栈
1(in)、1(out)、2(in)、2(0ut)、3(in)、3(out)
1(in)、1(out)、2(in)、3(in)、3(0ut)、2(out)
1.进一个出一个
2.一次进去，一次出来
3. 先进1，出1。2和3一次进
4.1,2一次进，一次出，3再进
5.1先进不出，2、3一次进，一次出，1再出
----------------------biu~biu~biu~~~在下问答机器人小D，这是我依靠自己的聪明才智给出的答案，如果不正确，你来咬我啊！
5种，公式是 (2n)!/(n!(n+1)!)，出栈顺序如下
为什么会是6呢？抛开公式不谈，你可以枚举。你要知道，如果是3第一个出栈的话，那么1，2的出栈顺序实际上已经确定了，也就是说3第一个出栈
只有一种情况。那么总的情况数应该是2+2+1=5
2687关注|623收录
2064关注|261收录
2335关注|1143收录
其他相似问题&&&&输出N个元素的所有出栈可能
&输出N个元素的所有出栈可能
1．有 5个元素，其入栈次序为：A、B、C、D、E，在各种可能的出栈次序中，以元素C第一个出栈，D第二个出栈的次序有哪几个？
若举报审核通过，可奖励20下载分
被举报人：
举报的资源分：
请选择类型
资源无法下载
资源无法使用
标题与实际内容不符
含有危害国家安全内容
含有反动色情等内容
含广告内容
版权问题，侵犯个人或公司的版权
*详细原因：
VIP下载&&免积分60元/年（1200次）
您可能还需要
Q.为什么我点的下载下不了，但积分却被扣了
A. 由于下载人数众多，下载服务器做了并发的限制。若发现下载不了，请稍后再试，多次下载是不会重复扣分的。
Q.我的积分不多了，如何获取积分？
A. 获得积分，详细见。
完成任务获取积分。
论坛可用分兑换下载积分。
第一次绑定手机，将获得5个C币，C币可。
关注并绑定CSDNID，送10个下载分
下载资源意味着您已经同意遵守以下协议
资源的所有权益归上传用户所有
未经权益所有人同意，不得将资源中的内容挪作商业或盈利用途
CSDN下载频道仅提供交流平台，并不能对任何下载资源负责
下载资源中如有侵权或不适当内容，
本站不保证本站提供的资源的准确性，安全性和完整性，同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
考试认证下载排行
您当前C币：0&&&可兑换 0 下载积分
兑换下载分:&
消耗C币:0&
立即兑换&&
兑换成功你当前的下载分为 。前去下载资源
你下载资源过于频繁，请输入验证码
如何快速获得积分？
你已经下载过该资源，再次下载不需要扣除积分
输出N个元素的所有出栈可能
所需积分：1
剩余积分：0
扫描微信二维码精彩活动、课程更新抢先知
VIP会员，免积分下载
会员到期时间：日
剩余下载次数：1000
输出N个元素的所有出栈可能
剩余次数：&&&&有效期截止到：
你还不是VIP会员VIP会员享免积分 . 专属通道极速下载
VIP下载次数已满VIP会员享免积分 . 专属通道极速下载，请继续开通VIP会员
你的VIP会员已过期VIP会员享免积分 . 专属通道极速下载，请继续开通VIP会员n&个元素顺序入栈，则可能的出栈序列有多少种？&转&
有关堆栈和Catalan数的思考
形如这样的直角三角形网格，从左上角开始，只能向右走和向下走，问总共有多少种走法？
问题的由来：编号为 1 到 n 的 n 个元素，顺序的进入一个栈，则可能的出栈序列有多少种？
对问题的转化与思考：n 个元素进栈和出栈，总共要经历 n 次进栈和 n 次出栈。这就相当于对这 2n 步操作进行排列。
一 个模型：一个 n*n
的正方形网格，从左上角顶点到右下角顶点，只能向右走和向下走。问共有多少种走法。如果将向右走对应上述问题的进栈，向下走对应上述问题的出栈，那么，可
以视此模型为对上述问题的具体描述。而解决此问题，只要在总共从左上角到右下角的2n步中，选定向右走的步数，即共有C(n
2n)中走法。
但是存在一个问题，如果走法越过了对角线，那么对应到上述问题是出栈数比入栈数多，这是不符合实际的。
对以上模型进行处理，对角线将以上正方形网格分成两部分，只留下包含对角线在内的下半部分，那么就不会出现越过对角线的问题。而这问题就是开始提出的问题。
-------------------------------------------------------
问题等价于：n个1和n个0组成一2n位的2进制数，要求从左到右扫描，1的累计数不小于0的累计数，试求满足这条件的数有多少？
解答： 设P2n为这样所得的数的个数。在2n位上填入n个1的方案数为 C（n 2n）
不填1的其余n位自动填以数0。从C（n 2n）中减去不符合要求的方案数即为所求。
不合要求的数指的是从左而右扫描，出现0的累计数超过1的累计数的数。
不合要求的数的特征是从左而右扫描时，必然在某一奇数2m+1位上首先出现m+1个的累计数，和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位数，必对应于一个不合要求的数。
用上述方法建立了由n＋1个0和n－1个1组成的2n位数，与由n个0和n个1组成的2n位数中从左向右扫描出现0的累计数超过1的累计数的数一一对应。
是由4个0和4个1组成的8位2进制数。但从左而右扫描在第5位（显示为红色）出现0的累计数3超过1的累计数2，它对应于由3个1，5个0组成的。
因而不合要求的2n位数与n＋1个0，n－1个1组成的排列一一对应，故有
P2n ＝ C（n 2n）— C（n＋1 2n）
这个结果是一个“卡塔兰数”Catalan，在组合数学中有介绍，可以参阅有关资料。
-----------------------------------------------------
是否可以用一种更合乎思维习惯的方式解决这个问题呢
可以把这个问题描述为一个二元组，(n, 0) 表示有n个元素等待进栈, 0 个元素已进栈, 这相当于问题最初的状况.
接着问题转化为(n-1,1). 可以这么说(n,0) = (n-1,1).
而对于(n-1,1)则相当于(n-1,0)+(n-2,2).
(n-1,0)表示栈中的一个元素出栈, (n-2, 2)表示又有一个元素入栈.
把问题一般话,则(n,m)的排列问题可以转化为(n,m-1)+(n-1,m+1) 此时m&=1,
因为必须栈中有元素才可以出栈.当m=0则(n,0)的问题只能转化为(n-1,1). 当问题为(0,
m)时得到递归边界,这个问题的解是只有一种排列.
#include &stdio.h&
#define ELEMNUM 6;
int getPermuStack(int n, int m)
if(n == 0)//递归边界
if(m == 0)//(n,0)问题的处理
return getPermuStack(n-1, 1);
return getPermuStack(n, m-1) + getPermuStack(n-1, m+1);
int main()
printf("The total count of stackout permutation is %d.",
getPermuStack(6, 0));
The total count of stackout permutation is 132.
-----------------------------------------------------
上面方法是可行的，但在实际编程中最好不要用递归，这样如果递归次数一多就容易造成栈溢出。你可以试下用较大的参数来调用你的函数，会造成runtime
而 且纯粹的递归会造成大量的重复计算：比如，你在计算getPermuStack(5, 5)的时候计算了getPermuStack(5,
4)，然后在计算getPermuStack(5,3)的时候又计算了一遍。当然可以通过动态规划的思想设置一个二维数组来记录计算结果，可是太消耗空
如果直观的方法就能很高效地解决问题的话，就不会有那么多人去从数学上求解了。
递归的致命缺点,也是优点就是把复杂的计算留给机器, 递归往往能迅速简洁的思维求出问题的解,
也许得到的算法是低效的.所以递归应该是一种懒人算法. 而"从数学上求解"应当是指从正向考虑问题的解,
递归是逆向求解.
已投稿到：
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。> 问题详情
有A，B，C，D，E 5个元素按次序入栈，在各种可能的出栈次序中，以元素C，D最先出栈的序列中，下列正确的
悬赏：0&答案豆
提问人：匿名网友
发布时间：
有A，B，C，D，E 5个元素按次序入栈，在各种可能的出栈次序中，以元素C，D最先出栈的序列中，下列正确的一组是( )。A．CDBAE CDABEB．CDEBA CDBEAC．CDEAB CDABED．CEBAE CDAEB请帮忙给出正确答案和分析，谢谢！
您可能感兴趣的试题
1已知一棵完全二叉树的第6层(设根为第1层)有8个叶结点，则完全二叉树的结点个数最多是(&&)。A.39B.52C.111D.1192将森林转换为对应的二叉树，若在二叉树中，结点u是结点v的父结点的父结点，则在原来的森林中，u和v可能具有的关系是(&&)。&Ⅰ．父子关系&Ⅱ．兄弟关系&Ⅲ．u的父结点与v的父结点是兄弟关系@A@只有Ⅱ@B@Ⅰ和Ⅱ@C@Ⅰ和Ⅲ@D@Ⅰ、Ⅱ和ⅢA.只有ⅡB.Ⅰ和ⅡC.Ⅰ和ⅢD.Ⅰ、Ⅱ和Ⅲ
我有更好的答案
论文写作技巧
相关考试课程
请先输入下方的验证码查看最佳答案
图形验证：
验证码提交中……算法（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网站的观点或立场
访问：13227次
排名：千里之外
原创：79篇
转载：16篇
(5)(1)(10)(9)(6)(28)(38)}