我要招人

去企业版

首页 > 试题广场 >

一个合法的表达式由()包围，()可以嵌套和连接，如(())(

[单选题]

一个合法的表达式由()包围，()可以嵌套和连接，如(())()也是合法表达式；现在有 6 对()，它们可以组成的合法表达式的个数为____

```
15
```
```
30
```
```
64
```
```
132
```
```
256
```
```
360
```

查看答案及解析

推荐

vieplivee

卡特兰数c(2n,n)-c(2n,n+1)=924-792=132

编辑于 2015-01-30 16:33:19 回复(4)

StrongYoung

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

=C(12,6)/7

=132

发表于 2015-08-08 22:34:34 回复(0)

牛客-007

答案：D

C(12,6)-C(12,5)=132

解释：

又是一个卡特兰数列。。。。这个解释起来真的挺麻烦。

我们可以把左括号看做1，右括号看做0，这些括号的组合就是01的排列

这里需要满足从第一个数开始的任意连续子序列中，0的个数不多于1的个数，也就是右括号的个数不多于左括号的个数。

假设我们不考虑这个限制条件，那么全部的01排列共有C（2n,n）种，也就是一半0一半1的情况

现在我们想办法把其中不符合要求的数量去掉

在任何不符合条件的序列中，找出使得0的个数超过1的个数的第一个0的位置，然后在导致并包括这个0的部分序列中，以1代替所有的0并以0代表所有的1。结果总的序列变成一个有(n+1)个1和(n-1)个0的序列。而且这个过程是可逆的，也就是说任何一个有(n+1)个1和(n-1)个0构成的序列都能反推出一个不符合条件的序列，所以不符合条件的序列个数为C（2n,n-1）

所以合法的排列数有C（2n,n）-C（2n,n-1）= C(12,6)-C(12,5)=132

编辑于 2015-01-17 17:43:09 回复(9)

buxizhizhou

对啊，卡特兰数。把左括号个数看成x轴，右括号个数看成y轴，相当于从（0,0）点到（6,6）点的不穿过y=x的非降路径个数。

而后者是C(2n,n)—C(2n,n-1)，即C(2n,n)/(n+1)

至于后者是怎么计算的，相当于这样的个数：

从（0,0）点到（6,6）点所有的个数减去从（-1,1）点到（6,6）点的所有路径个数

发表于 2015-09-04 23:31:04 回复(1)

SJ.M

static int count = 0;
static int n = 12;
void valid(int n,int sum){
	if (n == 0 && sum == 0){
		count++;
		return;
	}
	else if (n == 0){
		return;
	}
	int i;
	if (sum >= 0){
		for (i = 0; i < 2; ++i){
			switch (i){
			case 0:valid(n-1,sum +1); break;
			case 1:valid(n-1,sum - 1); break;
			}
		}
	}
	else{
		return;
	}
}

发表于 2015-08-15 19:06:29 回复(0)

薛定谔的熊

上面的高票答案没看太懂。。。在知乎上找了个解释

链接：https://www.zhihu.com/question/25072237/answer/30111179

编辑于 2016-09-07 18:44:07 回复(0)

bellz

咱们不管它是不是卡特兰好了

我们记F(m,n)为m个左括号和n个右括号时有多少种填法。

显然有m>=n。我们不妨考虑m,n>0的情况。

当m=n时，F(m,m)=F(m-1,m)（因为这时候第一个一定填的是左括号）

当m>n时，此时我们可以填一个左括号或者右括号，故有F(m,n)=F(m-1,n)+F(m,n-1)

边界条件方面，有F(1,n)=n。考虑1个左括号和n个右括号的情况，此时一共有n+1个位置，左括号显然不能填在末尾，所以有n种填法。

这个形式上和斐波拉契有点像，只不过是二维的，所以画一个表格会比较好求解一点。（一开始我直接手算，发现容易忘掉之前算的值。。）

画出来的矩阵大概是这个样子的，其中，打横的行表示右括号的数量n，打竖的列表示左括号的数量m。当m<n时F(m,n)的值没有意义，记为星号。

编辑于 2019-02-28 15:54:33 回复(0)

钜子墨苍离

动态规划题，或者栈相关题。动态规划的二维矩阵：

* * * * * 132

* * * * 42 132

* * * 14 42 90

* * 5 14 28 48

* 2 5 9 14 20

1 2 3 4 5 6

发表于 2015-08-25 16:12:17 回复(2)

Forrestcloud

卡特兰数：c(2n,n)-c(2n,n-1)=924-792=132

C(12,6)-C(12,5)=132

解释：

我们可以把左括号看做1，右括号看做0，这些括号的组合就是01的排列

这里需要满足从第一个数开始的任意连续子序列中，0的个数不多于1的个数，也就是右括号的个数不多于左括号的个数。

假设我们不考虑这个限制条件，那么全部的01排列共有C（2n,n）种，也就是一半0一半1的情况

现在我们想办法把其中不符合要求的数量去掉

所以合法的排列数有C（2n,n）-C（2n,n-1）= C(12,6)-C(12,5)=132

发表于 2017-09-25 21:47:54 回复(0)

会飞的大牛

卡特兰数公式：

编辑于 2017-03-23 11:24:08 回复(0)

东河西岸

卡特兰数C(2n,n)-C(2n,n-1)

发表于 2020-08-16 16:29:27 回复(0)

泽201907172250706

1对括号有1种组合方式，2对括号有2种组合方式，3对括号有【()()()；(())()；()(())；((()))；(()())】5种组合方式，符合卡特兰数特征：1、2、5

套公式 (2N)! / (N + 1)!N! = 12!/7!6! = 132

发表于 2019-07-29 16:49:39 回复(0)

~~Smile

#-*- coding: utf-8  s = [[] for i in range(13)]
i = 0  s[i] = [1] while i <= 11:  for j in s[i]:  if j-1 >= 0:   s[i+1].append(j-1)
        s[i+1].append(j+1)
    i = i + 1  #print([i for i in s[11] if i == 0].__len__())  以下的5行代码其实可以使用这一行解决，写下面那个为了方便理解，但是还是一行简单  count = 0 for i in s[11]:  if i ==0:   count +=1 print(count)

编辑于 2018-08-11 10:46:41 回复(0)

安科15计爱玲

卡特兰数C(2n,n)/(n+1)，本题n=6

发表于 2018-04-27 11:23:04 回复(0)

AABBCCDD123

太渣了 只能想到暴力遍历,,,,,,渣渣了

bool findfit(string str)
{
    stack<char> sta;

    for(int i = 0; i < str.size(); ++i)
    {
        if (str[i] == '0')
            sta.push(str[i]);
        else
        {
            if (!sta.empty())
                sta.pop();
            else
                return 0;
        }
    }

    return sta.empty() ? 1 : 0;
}

int main()
{
    int sum = 0;
    char str[] = "000000111111";
    do
    {
        string tmpstr(str);
        sum += findfit(tmpstr);
    }while(next_permutation(str, str+12));

    cout << sum << endl;
}

发表于 2018-04-10 19:10:08 回复(0)

初入java

#coding=utf-8
s=[[] for i in range(13)] #用来记录每前进s的z

i=0

s[i]=[1] #第一个括号一定是左括号

while i<=11:                    #计算12个括号引起的值变化
    #print i,s[i]
    for j in s[i]:
        if j-1>=0:              #若出现的右括号多于左括号，则值小于0
            s[i+1].append(j-1)
        s[i+1].append(j+1)
    i=i+1

print [i for i in s[11] if i == 0].__len__() #输出s[11]中0的个数，即为6对括号正确格式的总个数

发表于 2017-09-08 16:51:18 回复(0)

huixieqingchun

注意卡特兰数的作用。

发表于 2016-05-07 17:57:41 回复(0)

提交观点

问题信息

数理统计阿里巴巴组合数学

来自：阿里巴巴2015研发工...

难度：

17条回答 1581收藏 18589浏览

一个合法的表达式由()包围，()可以嵌套和连接，如(())(

问题信息

热门推荐

相关试题