卡特兰数又称卡塔兰数,英文名Catalan number。
是组合数学中一个常出现在各种计数问题中出现的数列。
以比利时的数学家欧仁·查理·卡塔兰 (1814–1894)的名字来命名,
其前几项为 : 
1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440,
9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 
91482563640, 343059613650, 1289904147324, 4861946401452, …

令h(0)=1,h(1)=1,catalan数满足递推式[1]  :
h(n)= h(0)h(n-1)+h(1)h(n-2) + … + h(n-1)h(0) (n>=2)
例如:h(2)=h(0)
h(1)+h(1)h(0)=11+11=2
h(3)=h(0)
h(2)+h(1)h(1)+h(2)h(0)=12+11+21=5
另类递推式[2]  :
h(n)=h(n-1)
(4*n-2)/(n+1);

递推关系的解为:
h(n)=C(2n,n)/(n+1) (n=0,1,2,…)

递推关系的另类解为:
h(n)=c(2n,n)-c(2n,n-1)(n=0,1,2,…)

void catalan() //求卡特兰数
{
    int i, j, len, carry, temp;
    a[1][0] = b[1] = 1;
    len = 1;
    for(i = 2; i <= 100; i++)
    {
        for(j = 0; j < len; j++) //乘法
        a[i][j] = a[i-1][j]*(4*(i-1)+2);
        carry = 0;
        for(j = 0; j < len; j++) //处理相乘结果
        {
            temp = a[i][j] + carry;
            a[i][j] = temp % 10;
            carry = temp / 10;
        }
        while(carry) //进位处理
        {
            a[i][len++] = carry % 10;
            carry /= 10;
        }
        carry = 0;
        for(j = len-1; j >= 0; j--) //除法
        {
            temp = carry*10 + a[i][j];
            a[i][j] = temp/(i+1);
            carry = temp%(i+1);
        }
        while(!a[i][len-1]) //高位零处理
        len --;
        b[i] = len;
    }
}
0
Posted in ACM

Leave a Comment:

电子邮件地址不会被公开。