卡特兰数

又是一个考验算法积累的题目，该题讨论的是卡特兰数的应用。

卡特兰数的使用条件为：h(n)=h(0)×h(n-1)+h(1)×h(n-1)+~~~+h(n-1)×h(0)

通式为：h(n)=(2×n)!/[(n+1)!×n!] (n>=2)

使用的情况有：如二叉树的个数，有序树的个数，多边形分成三角形的个数等。

如：排队的问题，十个人排两排，第一排的人比第二排的人低，有几种排法：

我们可以先把这10个人从低到高排列，然后，选择5个人排在第一排，那么剩下的5个人肯定是在第二排。

用0表示对应的人在第一排，用1表示对应的人在第二排，那么含有5个0，5个1的序列，就对应一种方案。

比如0000011111就对应着

第一排:0 1 2 3 4

第二排:5 6 7 8 9

0101010101就对应着

第一排:0 2 4 6 8

第二排:1 3 5 7 9

所以，看到问题相应的转换为，这样的满足条件的01序列有多少个。

观察规律我们发现1的出现前边必须有一个相应的0对应，所以从左到右的所有序列中0的个数要一直大于1的个数。那这种数列有多少种排列方式呢？

从左往右，假设第一个零的个数等于一的个数是在第k个数，那么k的左边一定0的个数不小于1的个数，共有k-1个数，在k的右边，应有n-k个数，这n-k个数也满足从左到右0的个数不小于1的个数。假设n个人的情况共h（n）个，那么左边h（k-1）个，右边h（n-k）个，共h（k-1）*h（n-k），k可取1~n，故是一个累加的过程，符合卡特兰数的规则。

在该题中，一共有n个结点的情况共有f（n）中，那么取一个结点为根结点，若左子树有k-1个结点，右子树就有n-k个节点，左子树共有f（k-1）种情况，右子树则有f（n-k）种，共有f(k-1)*f(n-k)种情况，k-1可以取到0~n故需累加，符合卡特兰数的规则。

卡特兰数的公式有多种

image.png image.png

由于多个求阶乘的方法太占用时间复杂度，所以应该对其进行一系列的变化，在将该通式变换后得：
c(n)=c(n-1)(4n-2)/(n+1)。可根据此式求解。

在解出卡特兰数以后，求出的是从根结点到叶子节点的安置方式，但是每个结点的安置顺序还是不确定的，因此还需要乘n！（所有节点的排序结果）

//输出卡特兰数 
//首先需要肯定，程序是正确的 
//这算是大数乘除法！记住他们是如何处理的！由于数据很大，用基本数据类型根本无法满足要求，只能用数组来表示！
#include "stdafx.h"
//典型的卡特兰数的应用
//判定二叉树的数量！假设有n个节点，一共有h(n)种数
//可以这样考虑：先选定一个节点为根节点，则还余下n-1个节点
//如果根节点左子树无节点，则右子树有n-1个节点
//如果左子树有1个节点，则右子树有n-2个节点~~~
//因此一共的种数是h(n)=h(0)*h(n-1)+h(1)*h(n-1)+~~~+h(n-1)*h(0)
//而这恰好是卡特兰数的表达式！卡特兰数一般的表达式为h(n)=(2*n)!/[(n+1)!*n!]  (n>=2)
//这道题使用的公式为c(n)=c(n-1)*(4*n-2)/(n+1);
#include <stdlib.h>
#include<iostream>
using namespace std;
#define MAX 101
#define BASE 10000

void multiply(int a[], int len, int b)//作用：四个数为一组，当大于四个数时，开始进位。乘法
{
    for (int i = len - 1, carry = 0;i >= 0;--i)
    {
        carry = carry + b*a[i];//h[i]项中存放的是h[i-1]的数字，故需要先将其本身乘以4*i-2，再除以i+1便可，这里进行的是乘项。
        a[i] = carry%BASE;//为了避免h[i]超过10000，所以会对其除10000取余，只存放小于10000的数位。
        carry = carry / BASE;//而carry变量将超出的位数记下，代表进位，并将这些超出的数加入到更高位中（参考与数学中列竖式进位）
    }//对于第一行的下一个四位乘后再加carry的情况，可以参考：100 2000 --》100 2000*6=601 2000==（100*10000+2000）*6=100*10000*6+2000*6
}//直到carry==0并且a[i~MAX]==0

void divide(int a[], int len, int b)//除法，从高位到低位，可参考与除法的竖式运算
{
    for (int i = 0, div = 0;i<len;i++)
    {
        div = div*BASE + a[i];
        a[i] = div / b;
        div = div%b;
    }
}


int main()
{
    int i, j, h[101][MAX];
    int a[MAX];
    memset(h[1], 0, MAX * sizeof(int));
    for (i = 2, h[1][MAX - 1] = 1;i <= 100;i++)
    {
        memcpy(h[i], h[i - 1], MAX * sizeof(int));//把第h[i+1]项放入h[i]中
        multiply(h[i], MAX, 4 * i - 2);
        divide(h[i], MAX, i + 1);
    }
    while (cin >> i && i >= 1 && i <= 100)
    {
        memcpy(a, h[i], MAX * sizeof(int));
        for (j = 2;j <= i;j++)
            multiply(a, MAX, j);//依次乘1*2*3…*n 为n个节点的自行排序结果。

        for (j = 0;j<MAX && a[j] == 0;j++);//自增到开始有数字的位数
            printf("%d", j, a[j++]);//这个位数是最高的一个四位数，故可能是小于四位的，故不需要加限制输出位数，格外输出
        for (;j<MAX;j++)
            printf("%04d", j, a[j]);//在已自增到可输出的位数后，在此基础上输出之后的相关四位数
        printf("\n");
    }//*/
    system("pause");
    return 0;
}

卡特兰数为1，1，2，5，14，42，132，429，1430，4862……
在推理失败时可以通过数字答案比对来验证题目是否为卡特兰数。