hdunbsp;1023,catalan,卡特兰数_综合

http://acm.hdu.edu.cn/showproblem.php?pid=1023

牛人总结：http://yanpol.blog.163.com/blog/static/4817080620106184553824/

#include <stdio.h>
int main()
{
int i,j,yu,temp,n,m,lenth;
int s[101][60];
s[1][1]=1;s[2][1]=2;
s[1][0]=1;s[2][0]=1;
lenth=s[2][0];//s[][0]为所求数字长度，初始为s[2]时（长度为1）,即s[2][0]=1;
for(i=3;i<=100;i++)
{
   yu=0;//指进位
   for(j=1;j<=lenth;j++)//乘法
   {
    temp=s[i-1][j]*(4*i-2)+yu;
    s[i][j]=temp;
    yu=temp/10;
   }
   while(yu)
   {
    s[i][++lenth]=yu;
    yu/=10;
   }

   yu=0;//在这指做除法时的余数
   for(j=lenth;j>=1;j--)//除法
   {
    temp=s[i][j]+yu*10;
    s[i][j]=temp/(i+1);
    yu=temp%(i+1);
   }
   while(!s[i][lenth])//除前面零
    lenth--;
   s[i][0]=lenth;
}
while(scanf("%d",&n)!=EOF)
{
   for(i=s[n][0];i>=1;i--)
    printf("%d",s[n][i]);
   printf("\n");
}
return 0;
}

h(n)= h(0)*h(n-1) + h(1)*h(n-2) + ... + h(n-1)h(0) (其中n>=2),这是n阶递推关系;
还可以化简为1阶递推关系: 如h(n)=(4n-2)/(n+1)*h(n-1)(n>1) h(0)=1
该递推关系的解为：h(n)=c(2n,n)/(n+1) (n=1,2,3,...)

//这道题还是有很大帮助的，虽说代码不算太难写，但是以前一直对大数除法没什么概念，以为很麻烦，

头一次写完后感觉还好，跟乘法差不多嘛，还有卡特兰数，也算一个小的系列吧，以后多看看，别忘了！！！

//找的相同问题：（自己想，想不出再想，再想不出看解释）

（1）有n个节点的不同形态的二叉树有多少种；
（2）把（严谨一点，凸的）n+2边形沿某几条对角线分割成n个三角形的方法数。
（3）排队买票问题。这是一个经典的问题，凡是高二及高二以上的都应该见过。2n个人排队买票，票价0.5元，有n个人拿的是1 元的钱，n个人拿的是0.5元的钱，售票处没有零钱，问有多少种排队方法，使得售票处不会出现找不出零钱的局面？（每个拿着1元钱的人看作是相同的，每个拿着0.5元钱的人也看作是相同的）
（4）现在有1,2,3..n这么多数来按顺序进栈了，但是什么时候从栈里取出数是没有要求的。这些数出栈的序列有几种呢？

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

（6）一位大城市的律师在她住所以北n个街区和以东n个街区处工作。每天她走2n个街区去上班。如果他从不穿越（但可以碰到）从家到办公室的对角线，那么有多少条可能的道路？

（7）*
　　 * *
　　 * * *
　　 * * * *
　　* * * * *

　　形如这样的直角三角形网格，从左上角开始，只能向右走和向下走，问总共有多少种走法？

（8）
n个1和n个0组成一2n位的2进制数，要求从左到右扫描，1的累计数不小于0的累计数，试求满足这条件的数有多少？

解释部分：

baike.baidu.com/view/1154333.htm

dfs35123.spaces.live.com/blog/cns!A6CB032EC0980F16!523.entry