首页 > 代码库 > 求解Catalan数，（大数相乘，大数相除，大数相加）
求解Catalan数，（大数相乘，大数相除，大数相加）
Catalan数
卡塔兰数是组合数学中一个常在各种计数问题中出现的数列。以比利时的数学家欧仁·查理·卡塔兰（1814–1894）命名。历史上，清代数学家明安图(1692年－1763年)在其《割圜密率捷法》最早用到“卡塔兰数”，远远早于卡塔兰。有中国学者建议将此数命名为“明安图数”或“明安图-卡塔兰数”。卡塔兰数的一般公式为 C(2n,n)/(n+1)。
性质：
令h(0)=1,h(1)=1，卡塔兰数满足递归式：
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)=P(2n,n)/(n+1)!=(2n)!/(n!*(n+1)!) (n=1,2,3,...)
卡塔兰数列的前几项为 [注： n = 0, 1, 2, 3, … n]
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, …
代码求解：
大数相加
1 //大数相加
2 string add(string s1,string s2)
3 {
4 if(s1.length()<s2.length())
5 {
6 string temp=s1;
7 s1=s2;
8 s2=temp;
9 }
10 int i,j;
11 for(i=s1.length()-1,j=s2.length()-1; i>=0; i--,j--)
12 {
13 s1[i]=char(s1[i]+(j>=0?s2[j]-‘0‘:0));
14 if(s1[i]-‘0‘>=10)
15 {
16 s1[i]=char((s1[i]-‘0‘)%10+‘0‘);
17 if(i) s1[i-1]++;
18 else s1=‘1‘+s1;
19 }
20 }
21 return s1;
22 }
大数相乘
1 //大数相乘
2 string mult(string a,string b)
3 {
4 int flag=0,i,j,k,p,q,t,max;
5 char ch;
6 string c,ans;
7 p=a.size()-1;
8 q=b.size()-1;
9 ans="0";
10 for(i=p; i>=0; i--)
11 {
12 flag=0;
13 c="";
14 for(j=i; j<p; j++) c+=‘0‘;
15 for(j=q; j>=0; j--)
16 {
17 t=(b[j]-‘0‘)*(a[i]-‘0‘)+flag;
18 flag=t/10;
19 c+=(t%10+‘0‘);
20 }
21 if(flag) c+=(flag+‘0‘);
22 for(j=0,k=c.size()-1; j<k; j++,k--)
23 {
24 ch=c[j];
25 c[j]=c[k];
26 c[k]=ch;
27 }
28 ans=add(ans,c);
29 }
30 return ans;
31 }
大数除以小数
1 //大数除以小数
2 string div(string src,int n)
3 {
4 string dest="";
5 int len = src.length(),i,k,t = 0 , s = 0;
6 bool flag = true;
7 for(i=0,k=0; i<len; i++)
8 {
9 t = s*10+(src[i]-48);
10 if(t/n>0 || t==0)
11 dest += (t/n+48),s = t%n,flag = false;
12 else
13 {
14 s = t;
15 if(!flag)
16 dest += ‘0‘;
17 }
18 }
19 return dest;
20 }
求解Catalan数
1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 #include <algorithm>
5 #include <cmath>
6 #include <vector>
7 #include <map>
8 #include<string.h>
9 #include<stack>
10 #include<set>
11 #include <queue>
12 using namespace std;
13 string s[120];
14
15 //大数相加
16 string add(string s1,string s2)
17 {
18 if(s1.length()<s2.length())
19 {
20 string temp=s1;
21 s1=s2;
22 s2=temp;
23 }
24 int i,j;
25 for(i=s1.length()-1,j=s2.length()-1; i>=0; i--,j--)
26 {
27 s1[i]=char(s1[i]+(j>=0?s2[j]-‘0‘:0));
28 if(s1[i]-‘0‘>=10)
29 {
30 s1[i]=char((s1[i]-‘0‘)%10+‘0‘);
31 if(i) s1[i-1]++;
32 else s1=‘1‘+s1;
33 }
34 }
35 return s1;
36 }
37
38 //大数相乘
39 string mult(string a,string b)
40 {
41 int flag=0,i,j,k,p,q,t,max;
42 char ch;
43 string c,ans;
44 p=a.size()-1;
45 q=b.size()-1;
46 ans="0";
47 for(i=p; i>=0; i--)
48 {
49 flag=0;
50 c="";
51 for(j=i; j<p; j++) c+=‘0‘;
52 for(j=q; j>=0; j--)
53 {
54 t=(b[j]-‘0‘)*(a[i]-‘0‘)+flag;
55 flag=t/10;
56 c+=(t%10+‘0‘);
57 }
58 if(flag) c+=(flag+‘0‘);
59 for(j=0,k=c.size()-1; j<k; j++,k--)
60 {
61 ch=c[j];
62 c[j]=c[k];
63 c[k]=ch;
64 }
65 ans=add(ans,c);
66 }
67 return ans;
68 }
69
70 //大数除以小数
71 string div(string src,int n)
72 {
73 string dest="";
74 int len = src.length(),i,k,t = 0 , s = 0;
75 bool flag = true;
76 for(i=0,k=0; i<len; i++)
77 {
78 t = s*10+(src[i]-48);
79 if(t/n>0 || t==0)
80 dest += (t/n+48),s = t%n,flag = false;
81 else
82 {
83 s = t;
84 if(!flag)
85 dest += ‘0‘;
86 }
87 }
88 return dest;
89 }
90 int main()
91 {
92 s[1]="1";
93 for(int i=2; i<101; i++)
94 {
95 char s1[10000];
96 sprintf(s1,"%d",4*i-2);
97 s[i] = mult(s[i-1],s1);
98 s[i] = div(s[i],i+1);
99 }
100 int n;
101 while(scanf("%d",&n))
102 {
103 if(n==-1) break;
104 cout<<s[n]<<endl;
105 }
106 return 0;
107 }
求解Catalan数，（大数相乘，大数相除，大数相加）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。