c++学习之卡特兰数_katelanshuc++

卡特兰数递推

C(n）=[2*（2n-1）/(n+1)] *c(n-1);
下面是洛谷P1044题解：

递推式11：
f[n]=f[0]*f[n-1] + f[1]*f[n-2] + … + f[n-1]*f[0] (n≥2)f[n]=f[0]∗f[n−1]+f[1]∗f[n−2]+…+f[n−1]∗f[0] (n≥2)
然后按照这个递推式模拟就好了(代码后面给)

既然上面标了1，那就有递推式2~

递推式2：
h[n]=h[n-1](4n-2)/(n+1)h[n]=h[n−1]∗(4∗n−2)/(n+1)
依旧按式子模拟(代码后面给)

既然有2，那再来个3吧~

递推式3：
h[n]=C[2n,n]/(n+1) (n=0,1,2,…)h[n]=C[2n,n]/(n+1)(n=0,1,2,…),CC是组合数

PS:C[m,n]=C[m-1,n-1]+C[m-1,n]PS:C[m,n]=C[m−1,n−1]+C[m−1,n]:且规定： C[n,0]=1 C[n,n]=1 C[0,0]=1C[n,0]=1C[n,n]=1C[0,0]=1
这个公式也叫组合数公式(下面那个也是)

（不知道组合数可以百度）

于是仍然把标程放到最后~

递推式4：
h[n]=C[2n,n]-C[2n,n-1] (n=0,1,2,…)h[n]=C[2n,n]−C [2n,n−1] (n=0,1,2,…) 组合数CC不解释了；

没有5了

但是有个Dalao写的组合数我没看懂，于是我搜集了各方资料，还是没看懂，不知道他写的组合数是怎么求的，虽然最后结果对了，但是组合数求出来都是错的(￣_￣|||)，不知道是不是巧合？

不管了，AC就好；（程序还是后面给~）

但是，出现了一个问题，上面介绍了四种公式，哪种最好？其实是第4种：如果这个数太大，那么题目可能会要求取模，那么第11种n太大的时候时空太大；第22种在取模运算中万一不小心整除了就凉了；第3种是除法运算，更行不通；唯有第4种,满足取模原则（加减无所谓），且不会出现倍数 WA 的情况，所以第4种解为最优解；

接着，比较上面四种做法：很明显的，递推式长得差得不多，它们都源于卡特兰思想，那么就没什么好说的了，只是时空复杂度的不同而已；

//数论做法 卡特兰数
//公式1：
#include<cstdio>
#define MAX_N 20
#define ll long long
using namespace std;
int n;
ll f[MAX_N];
int main()
{
    f[0]=f[1]=1;
    scanf("%d",&n);
    for(int i=2;i<=n;i++)
    {
        for(int j=0;j<i;j++)
        {
            f[i]+=f[j]*f[i-j-1];
        }
    }
    printf("%lld",f[n]);
    return 0;
}

//公式2：
#include<cstdio>
#define MAX_N 20
#define ll long long
using namespace std;
int n;
ll f[MAX_N];
int main()
{
    f[0]=f[1]=1;
    scanf("%d",&n);
    for(int i=2;i<=n;i++)
    {
        f[i]+=f[i-1]*(4*i-2)/(i+1);
    }
    printf("%lld",f[n]);
    return 0;
}

//公式3：
#include<cstdio>
#define MAX_N 20
#define ll long long
using namespace std;
int n;
ll c[MAX_N*2][MAX_N];
int main(){

    scanf("%d",&n);
    for(int i=1;i<=2*n;i++)
    {
        c[i][0]=c[i][i]=1;
        for(int j=1;j<i;j++)
        {
            c[i][j]=c[i-1][j]+c[i-1][j-1];
        }
    }
    printf("%lld",c[2*n][n]/(n+1));
    return 0;
}

//公式4： 
#include<cstdio>
#define MAX_N 20
#define ll long long
using namespace std;
int n;
ll c[MAX_N*2][MAX_N];
int main(){

    scanf("%d",&n);
    for(int i=1;i<=2*n;i++)
    {
        c[i][0]=c[i][i]=1;
        for(int j=1;j<i;j++)
        {
            c[i][j]=c[i-1][j]+c[i-1][j-1];
        }
    }
    printf("%lld",c[2*n][n]-c[2*n][n-1]);
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86