HDU1023 Train Problem II【Catalan数】

题目链接:

?pid=1023

题目大意:

一列N节的火车以严格的顺序到一个站里,问出来的时候有多少种顺序。

解题思路:

典型的求Catalan数的题目,但是结果会很大,所以需要用大数来解决。

Catalan公式为 h(n) = h(n-1) * (4*n-2) / (n + 1),,h(0) = h(1) = 1。

AC代码:

#include<iostream>#include<algorithm>#include<cstdio>#include<cstring>using namespace std;const int MAXN = 100;const int BASE = 10000;void Multiply(int A[], int Max, int b) //大数乘法 A[]*b 10000进制{int Array = 0;for(int i = Max – 1; i >= 0; –i){Array += b * A[i];A[i] = Array % BASE;Array /= BASE;}}void Divide(int A[], int Max, int b) //大数除法 A[]/b 10000进制{int Div = 0;for(int i = 0; i < Max; ++i){Div = Div * BASE + A[i];A[i] = Div / b;Div %= b;}}int A[MAXN+10][MAXN+10];int main(){memset(A,0,sizeof(A));A[1][99] = 1;for(int i = 2; i < 101; ++i){for(int j = 0; j < 100; ++j)A[i][j] = A[i-1][j];Multiply(A[i], MAXN, 4*i-2);Divide(A[i], MAXN, i+1);}int N;while(~scanf("%d",&N) && N != -1){int i;for(i = 0; i < MAXN && A[N][i] == 0; ++i); //去掉数组前导0printf("%d",A[N][i++]); //输出第一个非0数for(; i < MAXN; ++i) //输出后边的数,每位保持4位长度printf("%04d",A[N][i]);printf("\n");}return 0;}

版权声明:本文为博主原创文章,未经博主允许不得转载。

勇气执着的背负起那厚重的行囊,奔向远方。

HDU1023 Train Problem II【Catalan数】

相关文章:

你感兴趣的文章:

标签云: