catalan数。大数与小数的相乘和相除(hdu1134)
发布时间:2020-12-14 03:41:14 所属栏目:大数据 来源:网络整理
导读:题目意思就是求2N个数字,连N 条不相交的线的方案数. 此题考查的是 卡特兰数 ,由于卡特兰数很大,所以考虑大数处理。 卡特兰数的前几项为:h(0)=1;h(1)=1;h(2)=2;h(3)=5…… 卡特兰数的递推公式为:h(n)=h(n-1)*(4*n-2)/(n+1); 非递推公式为C(2n,n)/(n+1);
题目意思就是求2N个数字,连N 条不相交的线的方案数. 此题考查的是卡特兰数,由于卡特兰数很大,所以考虑大数处理。 卡特兰数的前几项为:h(0)=1;h(1)=1;h(2)=2;h(3)=5…… 卡特兰数的递推公式为:h(n)=h(n-1)*(4*n-2)/(n+1); 非递推公式为C(2n,n)/(n+1); 此题用递推公式求解,并用到大数的乘法和大数的乘法处理,本题对卡特兰数的前100项做了预处理: #include<iostream> //卡特兰数求法 递推公式h(n)=h(n-1)*(4*n-2)/(n-1) #include<cstdio> using namespace std; #include<string.h> #define N 100 //存一个卡特兰数的数组长度 #define M 10000 //以4位数存到 数组中的一个数中 int a[101][N]; void multiply(int a[],int n,int b)//大数乘法 { int i,aa=0; for(i=N-1;i>=0;i--) { aa=aa+b*a[i]; a[i]=aa%M; aa=aa/M; } } void divide(int a[],int b)//大数除法 { int div=0,i; for(i=0;i<N;i++) { div=div*M+a[i]; a[i]=div/b; div=div%b; } } int main() { int n,i; memset(a[1],sizeof(a[1]));// a[1][N-1]=1; //初始化第一个即当n=1时 for(i=2;i<101;i++) { memcpy(a[i],a[i-1],N*sizeof(int));//memcpy函数的恰到用处 multiply(a[i],N,4*i-2);//执行乘(4*n-2) h(n)=h(n-1)*(4*n-2) divide(a[i],i+1); //执行/(n+1) } while(scanf("%d",&n)!=EOF&&n!=-1) { for(i=0;i<N&&a[n][i]==0;i++);//去掉数组前面为0的元素 printf("%d",a[n][i++]);//输出不为0的第一个元素 for(i=i;i<N;i++)//输出后面的 printf("%04d",a[n][i]);//注意要用到"%04d",若不为4位数,前面补0 printf("n"); } return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |