A33834. 循环以及循环的嵌套，是同学们编写程序时常见的操作，如果用一对括号来代表一个循环的话那么三个循环出现的合法组合有 5 55 种，分别为∶ “{}{}{}”、"{{{}}}"、"{{}{}}"、"{{}}{}"、"{}{{}}"。
填空题
困难
知识点
题目描述
循环以及循环的嵌套，是同学们编写程序时常见的操作，如果用一对括号来代表一个循环的话那么三个循环出现的合法组合有 5 55 种，分别为∶ “{}{}{}”、"{{{}}}"、"{{}{}}"、"{{}}{}"、"{}{{}}"。
输入格式
输入一个数字n(1≤n≤30)，代表循环的个数。
输出格式
输出 n nn 个循环的合法组合数。
样例输入
3
样例输出
5
参考答案
#include <iostream>
using namespace std;
const int N = 65;
long long f[N][N];
//杨辉三角计算组合数
void init(int n)
{
//初始状态
for(int i = 0; i <= n; i ++)
{
f[i][0] = 1, f[i][i] = 1;
}
for(int i = 1; i <= n; i ++)
for(int j = 1; j < i; j ++)
f[i][j] = f[i - 1][j - 1] + f[i - 1][j];
}
int main()
{
int n;
cin >> n;
int m = 2 * n;
init(m); //预处理组合数
//卡塔兰数列求值C(2n, n) / (n + 1)
cout << f[m][n] / (n + 1) << endl;
return 0;
}
上一题
下一题