hdu 1023 Train Problem II(catalan 大数)uva 10303 uva 991
发布时间:2020-12-14 03:31:49 所属栏目:大数据 来源:网络整理
导读:hdu 1023: 经典的入栈时卡特兰数问题。 蓝桥杯决赛的时候遇见了,不会做,直接带的公式用计算器摁出的答案。 当时用的是这个公式: 今天用的是这个公式,并加上大数乘法与除法的写法: h(n) = (4 * n - 2 )/ (n + 1 )* h(n - 1) 另外附上卡特兰的经
hdu 1023: 经典的入栈时卡特兰数问题。 蓝桥杯决赛的时候遇见了,不会做,直接带的公式用计算器摁出的答案。 当时用的是这个公式: 今天用的是这个公式,并加上大数乘法与除法的写法: h(n) = (4 * n - 2 )/ (n + 1 )* h(n - 1) 另外附上卡特兰的经典总结:http://www.cnblogs.com/wuyuegb2312/p/3016878.html 代码: //h(n) = (4 * n - 2) / (n + 1) * h(n - 1) #include <stdio.h> int a[105][105]; void catalan() { a[1][0] = 1; a[1][1] = 1; a[2][0] = 1; a[2][1] = 2; int len = 1; for (int i = 3; i < 105; i++) { //乘法 int yu = 0; for (int j = 1; j <= len; j++) { int t = a[i - 1][j] * (4 * i - 2) + yu; a[i][j] = t % 10; yu = t / 10; } while (yu) { a[i][++len] = yu % 10; yu /= 10; } //除法 for (int j = len; j > 0; j--) { int t = a[i][j] + yu * 10; a[i][j] = t / (i + 1); yu = t % (i + 1); } //求位 while(!a[i][len]) len--; a[i][0] = len; } } int main() { int n; catalan(); while (scanf("%d",&n) != EOF) { for (int i = a[n][0]; i > 0; i--)//a[n][0] 表示该数的长度 printf("%d",a[n][i]); printf("n"); } return 0; } uva 10303: 题意: 给n个数字,能构建成多少种二叉排序树。 代码: //h(n) = (4 * n - 2) / (n + 1) * h(n - 1) #include <stdio.h> int a[1005][1005]; void catalan() { a[1][0] = 1; a[1][1] = 1; a[2][0] = 1; a[2][1] = 2; int len = 1; for (int i = 3; i < 1005; i++) { //乘法 int yu = 0; for (int j = 1; j <= len; j++) { int t = a[i - 1][j] * (4 * i - 2) + yu; a[i][j] = t % 10; yu = t / 10; } while (yu) { a[i][++len] = yu % 10; yu /= 10; } //除法 for (int j = len; j > 0; j--) { int t = a[i][j] + yu * 10; a[i][j] = t / (i + 1); yu = t % (i + 1); } //求位 while(!a[i][len]) len--; a[i][0] = len; } } int main() { #ifdef LOCAL freopen("in.txt","r",stdin); #endif // LOCAL int n; catalan(); while (scanf("%d",a[n][i]); printf("n"); } return 0; } 991: 题意: 圆内不相交弦的个数。 代码: //h(n) = (4 * n - 2) / (n + 1) * h(n - 1) #include <stdio.h> int a[105][105]; void catalan() { a[1][0] = 1; a[1][1] = 1; a[2][0] = 1; a[2][1] = 2; int len = 1; for (int i = 3; i < 105; i++) { //乘法 int yu = 0; for (int j = 1; j <= len; j++) { int t = a[i - 1][j] * (4 * i - 2) + yu; a[i][j] = t % 10; yu = t / 10; } while (yu) { a[i][++len] = yu % 10; yu /= 10; } //除法 for (int j = len; j > 0; j--) { int t = a[i][j] + yu * 10; a[i][j] = t / (i + 1); yu = t % (i + 1); } //求位 while(!a[i][len]) len--; a[i][0] = len; } } int main() { int n; catalan(); int ca = 0; while (scanf("%d",&n) != EOF) { if (ca++) printf("n"); for (int i = a[n][0]; i > 0; i--)//a[n][0] 表示该数的长度 printf("%d",a[n][i]); printf("n"); } return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |