hdu_1134_Game of Connections

hdu_1134_Game of Connections_卡特兰数列

参照：http://www.360doc.com/content/10/1010/16/3656934_59884964.shtml

卡特兰计算公式：

数列 a[n]=C(2n,n)/(n+1)
为了计算的方便将其推导为递推公式：a[n]=((4*n-2)/(n+1))*a[n-1];

将该递推式拆解为(4*n-2)与a(n-1)的乘积，再除以(n+1);

 1 #include<iostream>
 2 using namespace std;
 3 #define SIZE 100
 4 int main()
 5 {
 6     int a[101][SIZE]= {0}; //数组用来存放结果 并且初始化
 7     a[1][0] = 1;
 8     int i,j,r=0;
 9     int temp = 0,len = 1;  //len 表示当前最长的有效位数，初始化为1
10     for(i = 2; i <= 100; i++)//从第二项 到 第一百项， 用公式计算
11     {
12         for(j = 0; j < len; j ++)// 依次作乘法
13             a[i][j] = a[i-1][j]*(4*i-2);//从低位到高位
14         for(j = 0; j < len; j++)//对乘出来的结果 进行处理
15         {
16             temp = a[i][j] + r;
17             a[i][j] = temp%10;
18             r = temp/10;
19         }
20         while(r)              //对高位进行处理
21         {
22             a[i][len] = r%10;
23             r /= 10;
24             len++;
25         }
26         for(j = len-1,r = 0; j >= 0;j--)//模拟除法 从高位到低位
27         {
28             temp = r*10+a[i][j];
29             a[i][j] = temp/(i+1);
30             r = temp%(i+1);
31         }
32         while(!a[i][len-1])     //处理高位的 0 
33             len--;
34     }
35     int n;
36     while(cin>>n&&n!=-1)//
37     {
38         for(i = SIZE-1; !a[n][i];i--);
39             for(i;i>=0;i--)
40             cout<<a[n][i];
41             cout<<endl;
42     }
43     return 0;
44 }

杭电 1267：http://acm.hdu.edu.cn/search.php?action=listproblem

用到：a[i][j] = a[i-1][j] + a[i][j-1];

#include<iostream>
using namespace std;

int main()
{
    int n,m,i,j;
    __int64 a[21][21];
    memset(a,0,sizeof(a));
    for(i = 1; i < 21; i++)
        a[i][0] = 1;
    a[1][1] = 1;
    for(i = 2; i < 21; i++)
        for(j = 1; j <= i; j++)
        {
            a[i][j] = a[i-1][j] + a[i][j-1];
        }
    while(scanf("%d%d",&m,&n)!=EOF)
    {
        printf("%I64d\n",a[m][n]);
    }
    return 0;
}

卡特兰具体事例还可以参看：

http://blog.csdn.net/wchyumo2009/article/details/6773694