学步园

catalan数的简单应用： h(n) = ((4 * n - 2) * h(n - 1) / (n + 1)

/*<br /> Author: ACb0y<br /> Date: 2010-11-12<br /> Type: 这道题是简单的卡特兰数，满足递推公式h(n)=(4*n-2)*h(n-1)/(n+1);<br /> ProblemId: hdu 1023 Train Problem II<br /> Result: 3184349 2010-11-12 16:29:17 Accepted 1023 0MS 352K 1105 B G++ ACb0y<br /> */</p> <p>#include <iostream><br /> using namespace std;<br /> struct node {<br /> int data[200];<br /> int len;<br /> };<br /> int n;<br /> node ans[101];<br /> void print_ans(int pos) {<br /> for (int i = ans[pos].len - 1; i >= 0; --i) {<br /> printf("%d", ans[pos].data[i]);<br /> }<br /> printf("/n");<br /> }<br /> void get_ans() {<br /> int i, j;<br /> int up;<br /> ans[1].data[0] = 1;<br /> ans[1].len = 1;<br /> for (i = 2; i <= 100; ++i) {<br /> for (j = 0; j < ans[i - 1].len; ++j) {<br /> ans[i].data[j] = ans[i - 1].data[j] * (4 * i - 2);<br /> }<br /> ans[i].len = ans[i - 1].len;<br /> for (j = up = 0; j < ans[i].len; ++j) {<br /> up += ans[i].data[j];<br /> ans[i].data[j] = up % 10;<br /> up /= 10;<br /> }</p> <p> while (up) {<br /> ans[i].data[ans[i].len] = up % 10;<br /> up /= 10;<br /> ans[i].len++;<br /> }</p> <p> for (j = ans[i].len - 1, up = 0; j >= 0; --j) {<br /> up *= 10;<br /> up += ans[i].data[j];<br /> ans[i].data[j] = up / (i + 1);<br /> up %= (i + 1);<br /> }<br /> while (ans[i].data[ans[i].len - 1] == 0) {<br /> ans[i].len--;<br /> }<br /> }<br /> }<br /> int main() {<br /> #ifndef ONLINE_JUDGE<br /> freopen("in.txt", "r", stdin);<br /> #endif<br /> get_ans();<br /> while (scanf("%d", &n) != EOF) {<br /> print_ans(n);<br /> }<br /> return 0;<br /> }