HDU ACM 1134 Game of Connections / 1130 How Many Trees?（卡特兰数）

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

【题目链接】http://acm.hdu.edu.cn/showproblem.php?pid=1134

【解题背景】这题不会做，自己推公式推了一段时间，将n=3和n=4的情况列出来了，只发现第n项与第n-1项有关系，上网搜索的时候发现是组合数学中关于Catalan（卡特兰）数的运用.

以下资料来自网络，整理以备记录学习：

【来源链接】

http://baike.baidu.com/view/2499752.htm

http://blog.163.com/lz_666888/blog/static/1147857262009914112922803/

Catalan序列是一个整数序列，其通项公式是我们从中取出的Cn就叫做第 n 个 Catalan 数，前17个 Catalan 数分别是：

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670

令h(0) = 1,h(1) = 1，catalan 数满足递推式:

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

另类递归式：

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

该递推关系的解为：

h(n+1)=C(2n,n)/(n+1) (n=1,2,3,...)

Catalan序列主要有几类运用：

1.括号化问题：

矩阵链乘： P=a1×a2×a3×……×an，依据乘法结合律，不改变其顺序，只用括号表示成对的乘积，试问有几种括号化的方案？(h(n-1)种)

2.出栈次序问题：

一个栈(无穷大)的进栈序列为1,2,3,..n,有多少个不同的出栈序列?

类似：有2n个人排成一行进入剧场。入场费5元。其中只有n个人有一张5元钞票，另外n人只有10元钞票，剧院无其它钞票，问有多少中方法使得只要有10元的人买票，售票处就有5元的钞票找零？(将持5元者到达视作将5元入栈，持10元者到达视作使栈中某5元出栈)

3.将多边行划分为三角形问题：

将一个凸多边形区域分成三角形区域的方法数?

类似：在圆上选择2n个点,将这些点成对连接起来使得所得到的n条线段不相交的方法数?（也就是本题）

4.给顶节点组成二叉树的问题：

给定n个节点，能构成多少种不同的二叉树？

（能构成h（n）个,这个公式的下标是从h(0)=1开始的）

【随笔】：本来知道这个公式之后想打表打出100个Catalan数，将公式化简了一下且用代码尝试了一下：

if(n == || n == ){
printf("1\n");
continue;
}
int sum = ;
for(int t=*n-; t>n+; t-=)
sum *= t;
//func(int m)函数求m的阶乘，func_pow(int a, int b) 函数求a的b次方
printf("%d\n", sum*func_pow(, n/)/func(n/+n%));

后来发现这也是大数处理的问题，翻看之前自己写的大数相乘和大数相除的代码，发现写的很吃力，干脆上网找大数处理的若干代码，发现可以很简单的进行大数相乘及大数相除，即为现在的Ac源代码中的大数处理

源码来自：http://blog.163.com/lz_666888/blog/static/1147857262009914112922803/

#include<iostream>
#define MAX 100
#define BASE 10000 using namespace std; void multiply(int a[],int Max,int b) //大数乘法,注意参数的传递
{
int i,array=;
for (i = Max-; i >= ; i--)
{
array += b * a[i];
a[i] = array % BASE; // 数组每一位存放大数的四位数字
array /= BASE;
}
return;
} void divide(int a[], int Max, int b) //模拟大数除法
{
int i, div = ;
for (i = ; i < Max; i++)
{
div = div * BASE + a[i];
a[i] = div / b;
div %= b;
}
}
int main()
{
int a[][MAX],i, n;
memset(a[],,MAX*sizeof(int));
for (i=, a[][MAX-] = ; i < ; i++) // 高坐标存放大数低位
{
memcpy(a[i], a[i-], MAX * sizeof(int)); //h[i] = h[i-1];
multiply(a[i], MAX, * i - ); //h[i] *= (4*i-2);
divide(a[i], MAX, i + ); //h[i] /= （i+1）;
}
while (cin >> n && n != -)
{
for (i = ; i < MAX && a[n][i] == ; i++); //去掉数组前为0的数字。
cout << a[n][i++]; //输出第一个非0数
for (; i < MAX; i++)
{
printf("%04d",a[n][i]); //输出后面的数，并每位都保持4位长度!(32767)
}
cout << endl;
}
return ;
}