这道题也算是很经典的了,属于一个基本原理题,深刻理解了这种题,也就理解了一大堆相似的问题。
分析:n对括号,那么位置0出现的括号必然是“(”,和它配对的“)”可能出现在1,3,5,。。。。2n-1的位置上,设这个位置为2i+1, 则i的取值为从0到n-1.
因此若假设C(2n)指的是2n个括号(n对)的所有可能合法组合的个数,以及和位置0的左括号配对的右括号出现在位置2i+1上时,合法组合的个数为num(2i+1),那么:
C(2n)=所有num(2i+1)的和,
取i=0到n-1累加
而num(2*i+1)=f(2i)*f(2n-2i-2),i>0----基本组合运算
当i=0时,只需假设 C(0)=1,
num(2*i+1)=C(2i)*C(2n-2i-2)即num(1)=C(0)*C(2n-2)也能成立,所以可得:
C(2n)=所有C(2i)*C(2n-2i-2)的和,i从0累加到n-1, 其中n>=1, C(0)=1
这个数就是
,注意n>=1
这个数就叫卡特兰数。
下面推导怎么计算卡特兰数:
1.考虑n对括号,共有n个 ( 和n个)。
对于其全排列,可以看做是2n个空,将n个 ( 放入其中任意n个空中, 剩余的位置由 ) 填充,显然其全排列的个数为
C(n,2n)
2.在全排列中,包含一部分非法的排列,我们从中减去非法的排列个数,即可得到合法的排列数目。问题规模被缩小。考虑所有排列中,非法排列的个数。
3.先来观察非法排列的特性,我们假设(为1,)为-1,对于任意一个非法排列a1,a2 ... an ,比存在一个k,使得
a1+a2+a3..ak<0
因为如果这个和小于0,说明到k位置-1出现的次数比1多,即右括号出现的次数比左括号多,即该组合是非法的。
4. 对于一个非法排列,必存在一个k,使得a1+a2+a3..ak<0,给出一个n=3时具体的排列:
1, -1, 1, -1,-1, 1
在k=5时,出现了非法情况。
我们将1~5元素翻转,即1和-1置换,那么该序列就变成了
-1, 1, -1, 1, 1, 1
这个翻转的序列中,有n+1个1,n-1个-1
我们再观察这个翻转后的序列,对于有n+1个1,n-1个-1的排列,共有C(n+1,2n)种。而对于这种非法的排列:
总是存在一个最小的k,我们只需要从第1个到第k个元素翻转回去,就能变成对于有n个1,n个-1的情况下的非法排列。同样,每一个n个1,n个-1的情况下的非法排列也会对应一个n+1个1,n-1个-1的排列。
例如:
1, 1, 1, 1, -1, -1 --->从k=1翻转 -1,1,1,1,-1,-1
-1, 1, 1, 1, 1, -1 --->从k=2翻转 1,-1,-1,1,1,-1
(这里不是很容易理解,需要自己画图分析)
5.所以可以推得,非法排列的个数为C(n+1,2n),
6.最终可得结论:对于n对括号,合法的排列共有C(n,2n) - C(n+1,2n)种.
也就是(2n)!/(n+1)!(n)!, 也就是C(n,2n)/(n+1)
那么,怎么打印出所有的括号组合呢?和上面的推导没什么关系。。。
主要是位置0必须放”(“,后面的位置可以尝试着放”(“或”)“,然后就进入递归。
递归函数怎么共享数据呢?全局变量或者输入参数(因为函数的输入参数其实就是复制一份在函数的栈帧上,所以为了能共享数据,采用指针或者引用做参数)。
基本准则:在合法括号序列构建的每一步,都需要”(“的个数大于等于”)“的个数。
解法一:考察剩余的左右括号
vector
generateParenthesis(int n) {
vector vec;
string s;
generater(n,n,s,vec);
return vec;
}
void generater(int left, int right, string s,vector &vec){
if(left==0 && right==0){
vec.push_back(s);
return;
}
if(left>0){
generater(left-1,right,s+'(',vec);
}
if(right>left){
generater(left,right-1,s+')',vec);
}
}
解法二:考察用过的左右括号
char buf[50]={0};
print(int left, int right, int n){
if(left==n && right==n){
printf("%s\n",buf);
return;
}
if(left
buf[left+right-1]='(';
print(left+1,right,n);
}
if(left>right){
buf[left+right-1]=')';
print(left,right+1,n);
}
}
void fun(n){
print(0,0,n);
}
阅读(4125) | 评论(0) | 转发(0) |