N***m
发帖数: 4460 | 1 给定n=1，2，3，4，5。。。对括号，求所有的组合方法有多少种。
比如两对括号的情形，有两种，分别是:
[1] ()()
[2] (())
======================================
我能想到的就是递归。每次递归去掉不可能的组合以及重复的pattern，
但是这样的效率很低。求优化解法。 |
g**e
发帖数: 6127 | 2 贴个我以前写的，请各位师傅指点。还是用递归。
/**
* @param m # of left bracket
* @param n # of right bracket
*/
public ArrayList bracketPermute(int m, int n) {
ArrayList tmp = new ArrayList();
if (m>n)
return null;
if (m==0) {
String s = "";
while (n-- > 0) {
s += "}";
}
tmp.add(s);
return tmp;
}
ArrayList tmp2 = bracketPermute(m-1, n);
for(String t : tmp2) {
tmp.add("{"+t);
}
if (m <= n-1) {
tmp2 = bracketPermute(m, n-1);
for(String t : tmp2) {
tmp.add("}"+t);
}
}
return tmp;
}
【在 N***m 的大作中提到】
: 给定n=1，2，3，4，5。。。对括号，求所有的组合方法有多少种。
: 比如两对括号的情形，有两种，分别是:
: [1] ()()
: [2] (())
: ======================================
: 我能想到的就是递归。每次递归去掉不可能的组合以及重复的pattern，
: 但是这样的效率很低。求优化解法。
|
e****d
发帖数: 895 | 3 n! ?
【在 N***m 的大作中提到】
: 给定n=1，2，3，4，5。。。对括号，求所有的组合方法有多少种。
: 比如两对括号的情形，有两种，分别是:
: [1] ()()
: [2] (())
: ======================================
: 我能想到的就是递归。每次递归去掉不可能的组合以及重复的pattern，
: 但是这样的效率很低。求优化解法。
|
g*********s
发帖数: 1782 | 4 这种求所有的基本都是递归。
【在 N***m 的大作中提到】
: 给定n=1，2，3，4，5。。。对括号，求所有的组合方法有多少种。
: 比如两对括号的情形，有两种，分别是:
: [1] ()()
: [2] (())
: ======================================
: 我能想到的就是递归。每次递归去掉不可能的组合以及重复的pattern，
: 但是这样的效率很低。求优化解法。
|
X****r
发帖数: 3557 | 5 显然不是。递推式为
f(n) = \sum_{i=0}^{n-1} f(i)f(n-i-1)
初始条件
f(0) = f(1) = 1
或许可以算出通项公式吧，不过我好久不做这类题目了。
【在 e****d 的大作中提到】
: n! ?
|
X****r
发帖数: 3557 | 6 原题只问所有的组合方法有多少种，并没有让你真得把它们列出来。
【在 g*********s 的大作中提到】
: 这种求所有的基本都是递归。
|
g*********s
发帖数: 1782 | 7 n = 3, 4, 5的结果是多少？核对一下。
我的结果：
5 30 65
14 112 238
42 420 882
源码：
void print_legal_parentheses(int curr_pos, int pos_limit, int
left_count, std::vector& tag) {
#ifdef DEBUG
fprintf(stdout, "%d %d %d\n", curr_pos,
pos_limit, left_count);
#endif
if ( curr_pos == pos_limit ) {
for ( int i = 0; i < tag.size(); ++ i ) {
fprintf(stdout, "%c ", tag[i] == 0 ? '(' : ')');
}
fprintf(stdout, "\n");
return;
}
for ( int k = 0; k <= 1; ++ k ) {
int new_left_count = (k == 0 ? left_count + 1 :
left_count);
#ifdef DEBUG
fprintf(stdout, "%d %d %d\n", curr_pos,
pos_limit, new_left_count);
#endif
if ( curr_pos + 1 - new_left_count <= new_left_count &&
2 * new_left_count <= pos_limit ) {
tag[curr_pos] = k;
print_legal_parentheses(curr_pos + 1, pos_limit,
new_left_count, tag);
}
}
}
void print_legal_parentheses(int k) {
std::vector tag (2*k);
print_legal_parentheses(0, 2*k, 0, tag);
}
【在 g**e 的大作中提到】
: 贴个我以前写的，请各位师傅指点。还是用递归。
: /**
: * @param m # of left bracket
: * @param n # of right bracket
: */
: public ArrayList bracketPermute(int m, int n) {
: ArrayList tmp = new ArrayList();
:
: if (m>n)
: return null;
|
g*********s
发帖数: 1782 | 8 那就加强一下呗，反正是编程版。
【在 X****r 的大作中提到】
: 原题只问所有的组合方法有多少种，并没有让你真得把它们列出来。
|
g*********s
发帖数: 1782 | 9 你这个递推公式似乎忽略了重复的情况。
比如()()()可以是2+1也可以是1+2。
这应该是个经典组合计数问题。
【在 X****r 的大作中提到】
: 显然不是。递推式为
: f(n) = \sum_{i=0}^{n-1} f(i)f(n-i-1)
: 初始条件
: f(0) = f(1) = 1
: 或许可以算出通项公式吧，不过我好久不做这类题目了。
|
X****r
发帖数: 3557 | 10 http://en.wikipedia.org/wiki/Catalan_number
【在 X****r 的大作中提到】
: 显然不是。递推式为
: f(n) = \sum_{i=0}^{n-1} f(i)f(n-i-1)
: 初始条件
: f(0) = f(1) = 1
: 或许可以算出通项公式吧，不过我好久不做这类题目了。
|
X****r
发帖数: 3557 | 11 你没理解这个式子。
最左边的第一个符号必然是左括号。i是指这个左括号和它配对的右括号
里面有多少对括号。n-i-1就是剩下有多少对括号。
【在 g*********s 的大作中提到】
: 你这个递推公式似乎忽略了重复的情况。
: 比如()()()可以是2+1也可以是1+2。
: 这应该是个经典组合计数问题。
|
X****r
发帖数: 3557 | 12 可以用数学解决的问题就不应该用编程解决。
【在 g*********s 的大作中提到】
: 那就加强一下呗，反正是编程版。
|
g**e
发帖数: 6127 | 13 5 14 42
【在 g*********s 的大作中提到】
: n = 3, 4, 5的结果是多少？核对一下。
: 我的结果：
: 5 30 65
: 14 112 238
: 42 420 882
: 源码：
: void print_legal_parentheses(int curr_pos, int pos_limit, int
: left_count, std::vector& tag) {
: #ifdef DEBUG
: fprintf(stdout, "%d %d %d\n", curr_pos,
|
z****e
发帖数: 2024 | 14 an alternative：
参数curr_pos 可以不要，用tag的size替代。
每次pop回来。
【在 g*********s 的大作中提到】
: n = 3, 4, 5的结果是多少？核对一下。
: 我的结果：
: 5 30 65
: 14 112 238
: 42 420 882
: 源码：
: void print_legal_parentheses(int curr_pos, int pos_limit, int
: left_count, std::vector& tag) {
: #ifdef DEBUG
: fprintf(stdout, "%d %d %d\n", curr_pos,
|
