首页
题库
面试
求职
学习
竞赛
More+
所有博客
搜索面经/职位/试题/公司
搜索
我要招人
去企业版
登录 / 注册
首页
>
试题广场
>
字符 A 、 B 、 C 依次进入一个栈,按出栈的先后顺序组
[单选题]
字符
A
、
B
、
C
依次进入一个栈,按出栈的先后顺序组成不同的字符串,至多可以组成
( )
个不同的字符串?
14
5
6
8
查看正确选项
添加笔记
求解答(12)
邀请回答
收藏(293)
分享
15个回答
添加回答
0
im
5
发表于 2017-12-08 01:37:45
回复(0)
更多回答
21
牛客-120抢救中心
组合数学中的Catalan数, C(2n,n)/(n+1) (C(2n,n)表示2n里取n) 。
发表于 2017-10-06 10:00:40
回复(1)
16
cpppppp
证明下是卡塔兰数
使用递归法证明:
设f(n)为n个数
栈混洗可能的结果
。
对于一组数 1,2,3,4,5,...,k.,..,n
假设最后出栈的元素为k
过程一:那么k之前有 k-1个数比k小,对于这k-1个数,在k入栈之前,已经入栈且出栈,
栈混洗可能的结果是
f(k-1)
。
过程二:那么k之后有 n-k个数比k大,对于这n-k个数,在k出栈之前,
已经入栈且出栈
,
栈混洗可能的结果是
f(n-k)
。
这两个过程独立,对于此时的k,可能的排列有 f(k-1)* f(n-k)
种。
又因为 k的取值为1,2,3,...,n。所以有:
解这个递归式子,解得:f(n) =C(2n,n)/(n+1)
证明完成。
ps:直接求解这个递归式有一定难度,不过我们可以使用数学归纳法证明结果的正确性。先
计算f
(0
)正确,再假设
f
(n-1
)
正确,最后证明f
(n
)
正确。详细过程就不写啦。 (
=
。
=
)
编辑于 2019-01-22 15:16:13
回复(0)
15
Raoul1996
全部入栈之后出栈:CBA
部分入栈出栈:BAC,ACB,BCA
入栈一个立即出栈: ABC
CAB不存在,因为C出栈之后,AB已经出栈,且A不会在B之上
发表于 2017-10-16 23:33:10
回复(3)
6
小尾巴5
n个结点的二叉树有
个不同形态
n个不同元素进栈,出栈序列个数为
发表于 2021-10-24 16:27:21
回复(0)
4
那天ws
h(n)=c(2n,n)/(n+1) 种合法的出栈顺序。
发表于 2018-08-02 10:16:33
回复(0)
2
牛客869811174号
(6*5*4)/(3*2*1)/(3+1)=5
发表于 2022-09-15 16:05:09
回复(0)
2
ecjtu21-vr2班-liujun
我用树状结构分析每个元素的下一次操作情况就可以分析出来
发表于 2022-04-19 18:04:38
回复(0)
2
Cyril_KI
https://blog.csdn.net/Cyril_KI/article/details/108412075
发表于 2021-09-11 10:59:40
回复(0)
1
九千亿高尔基
考察栈的运用
发表于 2018-10-21 21:23:52
回复(0)
1
陈201808242003434
由该三个元素所组成的不同的元素组合为:3!=6种,然后再减去不可能出现的出栈顺序,不可能的出现顺序只有一种:C A B 。所以就是6-1=5种
发表于 2018-09-24 16:17:25
回复(0)
0
Scott_bob
又是卡特兰数
发表于 2022-11-18 21:31:41
回复(0)
0
鹿xs
可以使用:C(2n,n)/(n+1)得出出栈的组合个数。
发表于 2022-07-19 19:18:39
回复(0)
0
Mufasa
有个同学的答案是错误的
正确结果应该为
CAB、CBA
ABC、BAC
ACB
其中BCA是不存在的,应为C的前一个字母是B,先进后出、后进先出
发表于 2019-01-02 14:48:47
回复(2)
0
胖的不要不要的胖胖渣
可能情况: (2n)!/((n+1)n!*n!)
发表于 2018-08-27 22:23:13
回复(0)
这道题你会答吗?花几分钟告诉大家答案吧!
提交观点
问题信息
栈
上传者:
阿奻_
难度:
15条回答
293收藏
7752浏览
热门推荐
相关试题
体育课测验(二)
广度优先搜索(BFS)
拓扑排序
dfs
评论
(2)
游戏内数据分析涉猎的少,如何证明自...
评论
(1)
之前的经历中单品数据分析的经验丰富...
评论
(1)
什么样的人适合做数据分析
评论
(1)
2022 诺瓦科技 Perl re...
perl
System Verilog
评论
(1)
扫描二维码,关注牛客网
意见反馈
下载牛客APP,随时随地刷题