首页 > 试题广场 >

设输入序列为1,2,3，则经过栈的作用后可以得到()种不同的

[填空题]

设输入序列为：1,2,3，则经过栈的作用后可以得到1种不同的输出序列。

推荐

牛客-007

答案：5种
分别是：
123，入栈一个就出栈一个
132，1入栈出栈，23依次入栈，再出栈
213，12依次入栈，依次出栈，3出栈，3出栈，
231，12入栈，2出栈，3入栈，依次出栈
321，依次全部入栈，依次出栈

编辑于 2015-01-31 10:00:16 回复(0)

ttkl

catalan数问题

发表于 2015-03-09 20:03:35 回复(0)

张佃鹏

这是一个卡特兰数问题，http://blog.163.com/lz_666888/blog/static/1147857262009914112922803/

发表于 2015-08-04 21:57:47 回复(1)

牛客651205号

(C(n, 2n) )/(n+1)

编辑于 2019-02-18 16:20:35 回复(0)

晴天的鱼会飞

n个数顺序入栈，出栈序列有Cn种。Cn=[1/(n+1)*(2n)!/(n!)*(n!)]

发表于 2016-06-24 14:18:49 回复(0)

Radar

出栈可能的5种情况如下：

1 2 3 进 3 2 1出 ——第一种3 2 1

1 2 进 2出 3 进 3出 1出——第二种2 3 1
1 2 进 2出 1出 3进 3出——第三种2 1 3
1进 1出 2进 3进 3出 2出——第四种1 3 2
1进 1出 2进 2出 3进 3出——第五种1 2 3

发表于 2015-09-09 09:42:46 回复(1)

牛牛12315

C(2n,n)/(n+1) =(2n)!/(n!*(n+1)!) (n=1,2,3,...)

发表于 2015-09-05 20:10:09 回复(0)

小四

S=C(2n,n)-C(2n,n-1);

1.括号化问题。

矩阵链乘： P=a1×a2×a3×……×an，依据乘法结合律，不改变其顺序，只用括号表示成对的乘积，试问有几种括号化的方案？(h(n)种)

2.出栈次序问题。

一个栈(无穷大)的进栈序列为1,2,3,..n,有多少个不同的出栈序列?

类似：有2n个人排成一行进入剧场。入场费5元。其中只有n个人有一张5元钞票，另外n人只有10元钞票，剧院无其它钞票，问有多少中方法使得只要有10元的人买票，售票处就有5元的钞票找零？(将持5元者到达视作将5元入栈，持10元者到达视作使栈中某5元出栈)

3.将多边行划分为三角形问题。

将一个凸多边形区域分成三角形区域的方法数?

类似：一位大城市的律师在她住所以北n个街区和以东n个街区处工作。每天她走2n个街区去上班。如果她从不穿越（但可以碰到）从家到办公室的对角线，那么有多少条可能的道路？

类似：在圆上选择2n个点,将这些点成对连接起来使得所得到的n条线段不相交的方法数?

4.给顶节点组成二叉树的问题。

给定N个节点，能构成多少种不同的二叉树？

发表于 2015-08-14 14:32:20 回复(1)

在吃瓜的大学生很坦荡

在x-y坐标平面上，考虑两种一格一格的移动，每一次平移我们可以上移一格，也可以下移一格，左移或者右移也是一样。姑且这样定义：

右移U: (X,Y)——。(x+1,y) 上移U: (X,Y)——>(x,y+1)

现在问通过这两种移动每次移动一次，有多少种方法可以从点（0,0）移动到点（5,5），这显然是5个R和5个U的组合排列，共十次移动，10选5就可以了，C(10，5)

比如： RR

我们再加点限制，在这个过程中不可越过直线y=x，但可接触。于是你该知道，这样的限制意味着，移动到每一点时，所经过的R的个数一定大于或等于U的个数，如果小于则不合要求。

比如： RR

比如： RU

对于不符合限制条件的情形来说，我们先把它在第一次越过y=x点处断开，分为两个部分

RU U U R RRUU R

然后第一部分因为符合要求不变，第二部分做翻转操作，即R变U，U变R，于是得

RU R R U UURR U

其实这样的分法，我们可以想到，在第一次越过直线时分开，即会导致前面部分得U比R多一个，而后面部分的R会比U多一个，一翻转就是U比R多一个，如此，总共翻转序列后U就比R多出两个，比如此处R只有4个U却有5个。同样的道理，可知所有不满足条件的情形一一对应着4个R和6个U的排列情形，这些情况的个数就是10选4么，C(10，4)，现在你知道了，加上限制条件后方法数就是

N=C(10，5)-C(10，4)=45

于是，可以这样总结，对于任意正整数n，如果你想从点（0,0）移动到点（n,n)且不越过直线y=x的方法数为：

Kn=C(2n,n)-C(2n,n-1)

这个Kn就是传说中的卡特兰数，简单吧~~ K0=1,

-----------------------------------------------------------------------------

三、卡特兰数的应用

1.给乘积X1X,X3......Xn加括号的方法数

将问题转化一下，就是爬坐标，左括号数一定要大于或者等于右括号数

2.排列三个1和三个-1，使得从左到右部分和总是非负的方法数

将问题转化一下，就是加括号的方法数，排1的个数一定要大于或者等于排的-1个数

3.给定四个1和四个0，进行排列组合，使得从左往右读0的个数不超过1的个数

将问题转化为读括号，从左往右读，左括号一定要大于或等于右括号个数。

4.来个看起来复杂点的：将1 2 3 4 5 6排成两行，使得每行3个数，并且每行从左往右读值增加，每一列小数在上

我们可以想象， 1 2 3代表左括号， 4 5 6代表右括号，为了从左往右读值增加，方***有很多，但加上小数在上大数在下，就相当于左括号数总是大于或者等于右括号数么。假设这里的“左括号”少一个，那么下面一行对应会多一个左括号，而且因为值要求从小到大排列，即每行左括号总是在前，那么在上下对齐时，由于下面左括号要多，所以下行最后一个左括号肯定对齐着上行的右括号，是不符合要求的，但上面行的左括号要多这是没问题的。

5【阿里巴巴笔试题】：说16个人按顺序去买烧饼，其中8个人每人身上只有一张5块钱，另外8个人每人身上只有一张10块钱。烧饼5块一个，开始时烧饼店老板身上没有钱。 16个顾客互相不通气，每人只买一个。问这16个人共有多少种排列方法能避免找不开钱的情况出现。

将问题转化为：带5块钱的排前面的个数总是要大于带10块钱的人的个数，即C(16，8)-C(16，7)

6.【腾讯笔试题】在图书馆一共6个人在排队，3个还《面试宝典》一书，3个在借《面试宝典》一书，图书馆此时没有了面试宝典了，求他们排队的总数？

将问题转化为：还书的人总是要大于或等于借书的人，即C(6，3)-C(6，2)

7. 出栈次序问题

一个栈(无穷大)的进栈序列为1,2,3,..n,有多少个不同的出栈序列?

将问题转化为：入栈的数的个数总是要大于或者等于出栈数的个数。 C(2n，n)-C(2n，n-1)

8【阿里巴巴笔试题】 12个高矮不同的人,排成两排,每排必须是从矮到高排列,而且第二排比对应的第一排的人高,问排列方式有多少种?

C(12，6)-C(12，5)

发表于 2017-04-18 10:36:30 回复(0)

牛客329837716号

catalan:C(n,2n)/(n+1)

发表于 2020-04-20 19:44:47 回复(0)

山川异域-风月同天

如果不知道卡特兰数的知识(反正我不知道)，最快最准确的思路大概应该是这样: 栈最大容量是1或3，很显然，各1种出栈顺序栈最大容量是2的话，必须有两个连续的push，是push12，或者push23。显然是3种。共5种

编辑于 2017-06-05 00:55:54 回复(0)

TracyDragon

C(2n,n)/（n+1）

发表于 2017-04-01 21:38:39 回复(0)

跳梁小丑

答案：5 根据栈的后进先出（LIFO）分为以下五种情况： 1、2、3 1、3、2 2、1、3 2、3、1 3、2、1

判断栈的pop情况，需遵循卡特兰数

编辑于 2016-12-08 15:17:04 回复(0)

孙立鑫

C(2n,n)/（n+1）

发表于 2016-09-30 11:28:22 回复(0)

Ｍe怤畢炜eＭ

卡特兰数

发表于 2016-08-10 15:31:47 回复(0)

haru

公式：

result=(1/(n+1))*((2n!)/(2(n!)))

编辑于 2016-08-08 09:23:41 回复(0)

BAT收了我吧

C(2n,n)/(n+1)

发表于 2016-06-11 11:31:53 回复(0)

冰封无痕

卡特兰数问题：f(2n)=C(2n，n)/(n+1) 其中n=0,1,2......n

编辑于 2016-03-12 22:01:30 回复(0)

予我深拥

这种题最简单的方法是：首先列出所有可能排序情况，然后排除。

发表于 2016-03-08 18:34:02 回复(0)

syq1207

123

321

132

231

213

发表于 2015-09-11 14:54:22 回复(0)

唐若

卡特兰数: h(n)=C(2n,n)/(n+1) (n=0,1,2,...)

编辑于 2015-08-29 08:59:34 回复(0)

提交观点

问题信息

栈

来自：4399游戏2015校...

上传者：小牧魔法袋

难度：

22条回答 197收藏 23223浏览

设输入序列为1,2,3，则经过栈的作用后可以得到()种不同的

三、卡特兰数的应用

问题信息

热门推荐

相关试题