注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

力的博客

小歇一会 heiheidemaolv

 
 
 

日志

 
 

卡特兰(catalan)数与大数 HDU 1130&&1134&&1023  

2011-11-06 22:34:06|  分类: ACM/C/C++/OJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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

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

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

先抛开题目,研究一个卡特兰数,以下内容摘自百度百科。

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

卡特兰数又称卡塔兰数,是组合数学中一个常出现在各种计数问题中出现的数列。由以比利时的数学家欧仁·查理·卡塔兰 (1814–1894)命名。

卡特兰数  前几项为 (OEIS中的数列A000108): 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(1)=1,h(0)=1,catalan数满足递归式:
  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)=1*1+1*1=2
  h(3)=h(0)*h(2)+h(1)*h(1)+h(2)*h(1)=1*2+1*1+2*1=5
  另类递归式:
  h(n)=h(n-1)*(4*n-2)/(n+1);
  该递推关系的解为:
  h(n)=C(2n,n)/(n+1) (n=1,2,3,...)

卡特兰数的应用
  实质上都是递归等式的应用
括号化问题
  矩阵链乘: P=a1×a2×a3×……×an,依据乘法结合律,不改变其顺序,只用括号表示成对的乘积,试问有几种括号化的方案?(h(n)种)
出栈次序问题
  一个栈(无穷大)的进栈序列为1,2,3,…,n,有多少个不同的出栈序列?
  分析
  对于每一个数来说,必须进栈一次、出栈一次。我们把进栈设为状态‘1’,出栈设为状态‘0’。n个数的所有状态对应n个1和n个0组成的2n位二进制数。由于等待入栈的操作数按照1‥n的顺序排列、入栈的操作数b大于等于出栈的操作数a(a≤b),因此输出序列的总数目=由左而右扫描由n个1和n个0组成的2n位二进制数,1的累计数不小于0的累计数的方案种数。
  在2n位二进制数中填入n个1的方案数为c(2n,n),不填1的其余n位自动填0。从中减去不符合要求(由左而右扫描,0的累计数大于1的累计数)的方案数即为所求。
  不符合要求的数的特征是由左而右扫描时,必然在某一奇数位2m+1位上首先出现m+1个0的累计数和m个1的累计数,此后的2(n-m)-1位上有n-m个 1和n-m-1个0。如若把后面这2(n-m)-1位上的0和1互换,使之成为n-m个0和n-m-1个1,结果得1个由n+1个0和n-1个1组成的2n位数,即一个不合要求的数对应于一个由n+1个0和n-1个1组成的排列。
  反过来,任何一个由n+1个0和n-1个1组成的2n位二进制数,由于0的个数多2个,2n为偶数,故必在某一个奇数位上出现0的累计数超过1的累计数。同样在后面部分0和1互换,使之成为由n个0和n个1组成的2n位数,即n+1个0和n-1个1组成的2n位数必对应一个不符合要求的数。
  因而不合要求的2n位数与n+1个0,n-1个1组成的排列一一对应。
  显然,不符合要求的方案数为c(2n,n+1)。由此得出 输出序列的总数目=c(2n,n)-c(2n,n+1)=1/(n+1)*c(2n,n)。
  (这个公式的下标是从h(0)=1开始的)
  类似问题
  有2n个人排成一行进入剧场。入场费5元。其中只有n个人有一张5元钞票,另外n人只有10元钞票,剧院无其它钞票,问有多少中方法使得只要有10元的人买票,售票处就有5元的钞票找零?(将持5元者到达视作将5元入栈,持10元者到达视作使栈中某5元出栈)
凸多边形的三角剖分问题
  求将一个凸多边形区域分成三角形区域的方法数。
  类似:一位大城市的律师在她住所以北n个街区和以东n个街区处工作。每天她走2n个街区去上班。如果她从不穿越(但可以碰到)从家到办公室的对角线,那么有多少条可能的道路?
  类似:在圆上选择2n个点,将这些点成对连接起来使得所得到的n条线段不相交的方法数?
用给定节点组成二叉树的问题
  给定N个节点,能构成多少种不同的二叉树
  (能构成h(N)个)

这里可以总结出卡特兰数的应用方面:括号、出栈、凸多边形三角剖分、给定结点组二叉树。

1134 三角、1130二叉树、1023出栈。

这里就直接用卡特兰数的规律加大数加法乘法来解决。

代码如下:

  1. #include <stdio.h>
  2. #include <string.h>
  3. char temp[1100]={0},sum[1100]={0};
  4. int main()
  5. {
  6. void multipe(char a[],char b[]);
  7. void puls(char a[],char b[]);
  8. char result[110][1000] = {0};
  9. char tt[1100],hh[1100];
  10. int i,j,k;
  11. int n;
  12. result[0][0] = 49;
  13. result[1][0] = 49;
  14. for( i=2; i <= 101; i ++){
  15. result[i][0]='0';
  16. for(j = 0;j < i;j ++){
  17. memset(tt,0,sizeof(tt));
  18. memset(hh,0,sizeof(hh));
  19. strcpy(tt,result[j]);
  20. strcpy(hh,result[i-j-1]);
  21. multipe(tt,hh);
  22. puls(temp,result[i]);
  23. memset(result[i],0,sizeof(result[i]));
  24. for(k=0;sum[k];k++)
  25. result[i][k]=sum[k];
  26. }
  27. }
  28. while(scanf("%d",&n)!=EOF)
  29. printf("%s\n",result[n]);
  30. return 0;
  31. }
  32. void multipe(char a[],char b[])
  33. {
  34. int la,lb;
  35. char t[1000];
  36. int c[2000];
  37. int i,j,l;
  38. la=strlen(a);
  39. lb=strlen(b);
  40. memset(t,0,sizeof(t));
  41. strcpy(t,a);
  42. for(j=0,i=la-1;i>=0;i--) a[j++]=t[i];
  43. memset(t,0,sizeof(t));
  44. strcpy(t,b);
  45. for(j=0,i=lb-1;i>=0;i--) b[j++]=t[i];
  46. memset(c,0,sizeof(c));
  47. for(i=0;i<la;i++)
  48. for(j=0;j<lb;j++){
  49. c[i+j]+=(a[i]-48)*(b[j]-48);
  50. c[i+j+1]+=c[i+j]/10;
  51. c[i+j]%=10;
  52. }
  53. l=la+lb+1;
  54. while(l>=0&&!c[l]) l--;
  55. if(l<0) c[0]=0;
  56. memset(temp,0,sizeof(temp));
  57. if(l<0) temp[0]='0';
  58. for(i=l,j=0;i>=0;i--,j++)
  59. temp[j]=c[i]+48;
  60. }
  61. void puls(char a[],char b[])
  62. {
  63. int i,j,k1,la,lb,s,lsum;
  64. int c=0;
  65. char h;
  66. for(j=0;a[j];j++); la=j-1;
  67. for(j=0;b[j];j++); lb=j-1;
  68. memset(sum,0,sizeof(sum));
  69. k1=0;
  70. while(1){
  71. if(la<0&&lb<0) break;
  72. else if(la<0) s=b[lb--]-48;
  73. else if(lb<0) s=a[la--]-48;
  74. else s=a[la--]-48+b[lb--]-48;
  75. if(k1==0) {sum[k1]=s%10+48 ;c=s/10;}
  76. else {sum[k1]=(s+c)%10+48;c=(s+c)/10;}
  77. k1++;
  78. }
  79. if(c!=0) sum[k1]=c+48;
  80. lsum=strlen(sum)-1;
  81. for(i=0;i<=lsum/2;i++)
  82. {h=sum[i];sum[i]=sum[lsum-i];sum[lsum-i]=h;}
  83. }

(代码不是自己写的,kuangye所写,三道题一个代码,HDU 1134判断下输入n!=-1)

http://www.cnblogs.com/kuangbin/archive/2012/03/21/2410516.html
  评论这张
 
阅读(519)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018