代码编织梦想

题目描述

循环以及循环的嵌套,是同学们编写程序时常见的操作,如果用一对括号来代表一个循环的话那么三个循环出现的合法组合有 5 5 5 种,分别为∶ “{}{}{}”、"{{{}}}"、"{{}{}}"、"{{}}{}"、"{}{{}}"。

输入格式

输入一个数字 n ( 1 ≤ n ≤ 30 ) n(1\le n\le 30) n(1n30)代表循环的个数。

输出格式

输出 n n n 个循环的合法组合数。

样例输入

3

样例输出

5

算法思想(Catalan数列)

根据题目描述求循环嵌套中括号的合法组合,这是一个典型的Catalan数列求值问题,公式推导可以参考我的另一篇题解:满足条件的01序列。因此因此,可以套用公式直接计算,通项公式为:

C a t a l a n ( n ) = C 2 n n n + 1 Catalan(n) = \frac{C_{2n}^{n}}{n + 1} Catalan(n)=n+1C2nn

代码实现

#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;
}

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 本文链接: https://blog.csdn.net/qiaoxinwei/article/details/111355948

应用费马小定理快速求得大指数对p取模-爱代码爱编程

费马小定理(Fermat’s little theorem)是数论中的一个重要定理,在1636年提出。如果p是一个质数,而整数a不是p的倍数,则有a^(p-1)≡1(mod p)。 快速幂超时 k = 998244353 def fpow(a, b): ans = 1 while b > 0: if b % 2

数学知识-核函数的通俗解释实例-爱代码爱编程

1.核函数本质 核函数其实准确来说就是一个内积(低维和高维的内积相等),相似度,和那个映射函数没有任何关系(因为有时候你根本找不到那个映射函数),即使找到了映射函数也没啥意义。比如说你想把二维映射到三维,自己凑项数恰好凑成了二次多项式函数,最大的意义就是让你看清楚了原理。你的根本目的就是图个省事在低维空间里面算 然后再说一下英文里kernel trick

数学知识-SVD-矩阵奇异值分解-爱代码爱编程

1 简介 SVD 全称:Singular Value Decomposition。SVD 是一种提取信息的强大工具,它提供了一种非常便捷的矩阵分解方式,能够发现数据中十分有意思的潜在模式。 主要应用领域包括: 隐性语义分析 (Latent Semantic Analysis, LSA) 或隐性语义索引 (Latent Semantic Indexin

C++题解: 满足条件的01序列-爱代码爱编程

Catalan数 费马小定理 快速幂求逆元 题目描述 给定 n n n 个 0

[AcWing],数学知识(二),证明推导欧拉函数,快速幂,扩展欧几里得算法-爱代码爱编程

数学知识,证明推导欧拉函数,快速幂,扩展欧几里得算法 欧拉函数欧拉公式筛法求欧拉函数快速幂快速幂快速幂求逆元扩展欧几里得算法线性同余方程 https://www.acwing.com/activity/content/punch_the_clock/11/ 欧拉函数 欧拉公式 对于每一个数

正态分布与泊松分布的关系-爱代码爱编程

正态分布 正态分布(normal distribution)又名高斯分布(Gaussian distribution)、正规分布,是一个非常常见的连续概率分布。正态分布在统计学上十分重要,经常用在自然和社会科学来代表一个不明的随机变量。 若随机变量X服从一个位置参数为 μ