我要招人

去企业版

首页 > 试题广场 >

字符 A 、 B 、 C 依次进入一个栈，按出栈的先后顺序组

[单选题]

字符 A 、 B 、 C 依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成 ( ) 个不同的字符串？

```
14
```
```
5
```
```
6
```
```
8
```

查看答案及解析

牛客-120抢救中心

组合数学中的Catalan数， C(2n,n)/(n+1) （C(2n,n)表示2n里取n）。

发表于 2017-10-06 10:00:40 回复(1)

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) = \sum_{k=1}^{n}{ f(k-1)* f(n-k) }$

解这个递归式子，解得：f(n) =C(2n,n)/(n+1)

证明完成。

ps：直接求解这个递归式有一定难度，不过我们可以使用数学归纳法证明结果的正确性。先计算f(0)正确，再假设f(n-1)正确，最后证明f(n)正确。详细过程就不写啦。（=。=）

编辑于 2019-01-22 15:16:13 回复(0)

Raoul1996

全部入栈之后出栈：CBA

部分入栈出栈：BAC，ACB，BCA

入栈一个立即出栈： ABC

CAB不存在，因为C出栈之后，AB已经出栈，且A不会在B之上

发表于 2017-10-16 23:33:10 回复(3)

小尾巴5

n个结点的二叉树有

个不同形态

n个不同元素进栈,出栈序列个数为

发表于 2021-10-24 16:27:21 回复(0)

那天ws

h(n)=c(2n,n)/(n+1) 种合法的出栈顺序。

发表于 2018-08-02 10:16:33 回复(0)

牛客869811174号

(6*5*4)/(3*2*1)/(3+1)=5

发表于 2022-09-15 16:05:09 回复(0)

ecjtu21-vr2班-liujun

我用树状结构分析每个元素的下一次操作情况就可以分析出来

发表于 2022-04-19 18:04:38 回复(0)

Cyril_KI

https://blog.csdn.net/Cyril_KI/article/details/108412075

发表于 2021-09-11 10:59:40 回复(0)

九千亿高尔基

考察栈的运用

发表于 2018-10-21 21:23:52 回复(0)

陈201808242003434

由该三个元素所组成的不同的元素组合为:3！=6种，然后再减去不可能出现的出栈顺序，不可能的出现顺序只有一种:C A B 。所以就是6-1=5种

发表于 2018-09-24 16:17:25 回复(0)

Scott_bob

又是卡特兰数

发表于 2022-11-18 21:31:41 回复(0)

鹿xs

可以使用:C(2n,n)/(n+1)得出出栈的组合个数。

发表于 2022-07-19 19:18:39 回复(0)

Mufasa

有个同学的答案是错误的

正确结果应该为
CAB、CBA
ABC、BAC
ACB

其中BCA是不存在的，应为C的前一个字母是B，先进后出、后进先出

发表于 2019-01-02 14:48:47 回复(2)

胖的不要不要的胖胖渣

可能情况： (2n)!/((n+1)n!*n!)

发表于 2018-08-27 22:23:13 回复(0)

发表于 2017-12-08 01:37:45 回复(0)

提交观点

问题信息

栈

上传者：阿奻_

难度：

15条回答 290收藏 7726浏览

字符 A 、 B 、 C 依次进入一个栈，按出栈的先后顺序组

问题信息

热门推荐

相关试题