大数 卡特兰数
发布时间:2020-12-14 02:57:29 所属栏目:大数据 来源:网络整理
导读:卡特兰数的公式为:?f[n]=f[n-1]*(4*i-2)/(i+1),由于数一大就需要用大数,下面为代码: #includeiostreamusing namespace std;const int maxn = 110;int a[maxn][maxn]; //a[i][j] a[i]表示第几个卡特兰数,a[i][j]表示第i个卡特兰数的第j位int b[maxn];//卡特
卡特兰数的公式为:?f[n]=f[n-1]*(4*i-2)/(i+1),由于数一大就需要用大数,下面为代码: #include<iostream> using namespace std; const int maxn = 110; int a[maxn][maxn]; //a[i][j] a[i]表示第几个卡特兰数,a[i][j]表示第i个卡特兰数的第j位 int b[maxn]; //卡特兰数的长度 void ktl() { int i,j,len,carry,tmp; a[1][0] = b[1] = 1; len = 1; for (i = 2; i <= 100; i++) { for (j = 0; j < len; j++) //乘法 a[i][j] = a[i - 1][j] * (4 * i - 2); carry = 0; for (j = 0; j < len; j++) { tmp = carry + a[i][j]; a[i][j] = tmp % 10; carry = tmp / 10; } while (carry) { a[i][len++] = carry % 10; carry /= 10; } for (j = len - 1; j >= 0; j--) { tmp = carry * 10 + a[i][j]; a[i][j] = tmp / (i + 1); carry = tmp % (i + 1); } while (!a[i][len - 1]) len--; b[i] = len; } } int main() { int n; ktl(); while (cin >> n) { for (int i = b[n] - 1; i >= 0; i--) cout << a[n][i]; cout << "n"; } } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |