当前位置: 代码迷 >> 综合 >> hdunbsp;1023,catalan,卡特兰数
  详细解决方案

hdunbsp;1023,catalan,卡特兰数

热度:70   发布时间:2024-01-04 11:11:16.0

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