HDU 1023 Train Problem II 大数打表Catalan数
发布时间:2020-12-14 03:04:52 所属栏目:大数据 来源:网络整理
导读:一个出栈有多少种顺序的问题。一般都知道是Catalan数了。 问题是这个Catalan数很大,故此需要使用高精度计算。 而且打表会速度快很多,打表公式要熟记: Catalan数公式 Cn=C(2n,n) / (n+1); 递推公式 C(n ) = C(n-1)*(4*n-2) / (n+1) 高精度乘以一个整数和高
一个出栈有多少种顺序的问题。一般都知道是Catalan数了。 问题是这个Catalan数很大,故此需要使用高精度计算。 而且打表会速度快很多,打表公式要熟记: Catalan数公式 Cn=C(2n,n) / (n+1); 高精度乘以一个整数和高精度除以一个整数的知识,这样还是使用整数数组比较好计算,如果使用string那么就不太好计算了,因为整数也可能是多位的。 const int MAX_N = 101; short catalan[MAX_N][MAX_N];//catlans[i][0] save the length void calCatalans() { short carry = 0,len = 1; catalan[1][0] = 1; catalan[1][1] = 1; catalan[2][0] = 1; catalan[2][1] = 2; for (int i = 3; i < MAX_N; i++) { carry = 0; for (int j = 1; j <= len; j++)//高精度乘以一个整数 { short sum = catalan[i-1][j]*((i<<2)-2) + carry; carry = sum / 10; catalan[i][j] = sum % 10; } while (carry) { catalan[i][++len] = carry % 10; carry /= 10; } for (int j = len; j > 0; j--)//高精度除以一个整数 { short sum = catalan[i][j] + carry*10; catalan[i][j] = sum / (i+1); carry = sum % (i+1);//一定能除尽,故此无需考虑余数情况 } while (catalan[i][len] == 0) len--; catalan[i][0] = len; } } int main() { calCatalans(); int n; while (~scanf("%d",&n)) { for (int i = catalan[n][0]; i > 0; i--) { printf("%d",catalan[n][i]); } putchar('n'); } return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |