当你的才华
还撑不起你的野心时,那你就应该静下心来学习

卡特兰数

卡特兰数


首先,我们设f(n)=序列个数为n的出栈序列种数。(我们假定,最后出栈的元素为k,显然,k取不同值时的情况是相互独立的,也就是求出每种k最后出栈的情况数后可用加法原则,由于k最后出栈,因此,在k入栈之前,比k小的值均出栈,此处情况有f(k-1)种,而之后比k大的值入栈,且都在k之前出栈,因此有f(n-k)种方式,由于比k小和比k大的值入栈出栈情况是相互独立的,此处可用乘法原则,f(n-k)*f(k-1)种,求和便是Catalan递归式。看到大家的题解都写到了卡特兰数,但是没有细细的讲讲这跟本题有什么关系本题的描述十分简单。n个数依次进栈,可随机出栈。求有几种可能。

dfs可以解,但是递推仿佛好像如同看上去貌似更简单一些。

解释一下原理:建立数组f。f[i]表示i个数的全部可能性。f[0] = 1, f[1] = 1; //当然只有一个设 x 为当前出栈序列的最后一个,则x有n种取值由于x是最后一个出栈的,所以可以将已经出栈的数分成两部分 1. 比x小 2. 比x大

比x小的数有x-1个,所以这些数的全部出栈可能为f[x-1]

比x大的数有n-x个,所以这些数的全部出栈可能为f[n-x]

这两部分互相影响,所以一个x的取值能够得到的所有可能性为f[x-1] * f[n-x]

另外,由于x有n个取值,所以

ans = f[0] * f[n-1] + f[1] * f[n-2] + … + f[n-1] * f[0];

这,就是传说中的卡特兰数附上代码:

#include <cstdio>
int n, f[30];
int main()
{
    //递推实现卡特兰数
    scanf("%d", &n);
    f[0] = 1, f[1] = 1;
    for(int i=2; i<=n; i++)
    for(int j=0; j<i; j++)
    f[i] += f[j] * f[i-j-1]; //递推公式    //f(2)=f(0)*f(1)+f(1)*f(0);
    printf("%d", f[n]);
    return 0;
}

卡特兰数

这是一道经典的卡特兰数例题

卡特兰数有四个公式,显然这题数据太水都可过,但我们要分析每个公式的用处。

以下内容神犇请无视(话说神犇也不会看这种水题的题解)

公式一

递归公式

h(0)=h(1)=1

h(n)= h(0) * h(n-1)+h(1) * h(n-2) + … + h(n-1) * h(0) (n>=2)

如果我们用这个公式显然我们要使用递归算法,那么数据一大就在时空上很麻烦

公式二

递推公式

h(n) = h(n-1) * (4 * n-2) / (n+1)

这个公式应用递推,看上起十分和善

但对大数据呢?

我们注意到大数据的时候h(n)会很大,这时候题目一般会让你对某素数取模(当然你可以打高精度(划掉))

但你在取模过程中难保一个 h(n) % mod = 0

那么根据公式下面所有的数都会等于0,于是你就愉快的WA了

公式三

组合数公式1

h(n) = C(2n,n) / (n+1) (n=0,1,2,…)

卡特兰数可以与组合数联系起来,得到上面的公式

而组合数就是一个杨辉三角,可以递推得到(这个不属于这道题的讨论范围我假装你们都会(逃))

但我们发现对于大数据你要取模,而对于除法你是没办法用膜的性质的(当然你可以应用逆元(划掉)),所以造成了麻烦

公式四

组合数公式2

h(n) = c(2n,n) – c(2n,n-1) (n=0,1,2,…)

与组合数公式1不同这个是两个组合数的减法

减法是可以用膜的性质的,于是你可以愉快的AC了。

所以我写了这么多就是想说,对于一个特定的任务,可能会有很多方法求解,但其实只要稍稍分析一下就会发现有一种方法是通用而优美的,我在没认真思考前都是记的四个公式,但是有一天我真的认真想过后才发现其实我就记住公式四就好了。

所以学习啊,还是要学会认真思(tou)考(lan):

#include<cstdio>
#define siz 20
using namespace std;

int n;
int c[siz*2][siz];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=2*n;i++) c[i][1]=c[i][i]=1;
    for(int i=3;i<=2*n;i++)
    for(int j=2;j<i;j++)
    c[i][j]=c[i-1][j]+c[i-1][j-1];
    printf("%d",c[2*n][n]-c[2*n][n-1]);
    return 0;
}
赞(3) 打赏
未经允许不得转载:啾啾鸟 » 卡特兰数

欢迎来到Birdjiujiu

欢迎刷题

阿巴阿巴阿巴

微信扫一扫打赏