首页 > 试题广场 >

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

[填空题]
设输入序列为:1,2,3,则经过栈的作用后可以得到1种不同的输出序列。
推荐
答案:5种
分别是:
123,入栈一个就出栈一个
132,1入栈出栈,23依次入栈,再出栈
213,12依次入栈,依次出栈,3出栈,3出栈,
231,12入栈,2出栈,3入栈,依次出栈
321,依次全部入栈,依次出栈
编辑于 2015-01-31 10:00:16 回复(0)
catalan数问题
发表于 2015-03-09 20:03:35 回复(0)
发表于 2015-08-04 21:57:47 回复(1)
(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)
出栈可能的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)
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)
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)
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)
卡特兰数
发表于 2016-08-10 15:31:47 回复(0)
公式:
result=(1/(n+1))*((2n!)/(2(n!)))
编辑于 2016-08-08 09:23:41 回复(0)
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)
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)