As we all know the Train Problem I, the boss of the Ignatius Train Station want to know if all the trains come in strict-increasing order, how many orders that all the trains can get out of the railway.

The input contains several test cases. Each test cases consists of a number N(1<=N<=100). The input is terminated by the end of file.

For each test case, you should output how many ways that all the trains can get out of the railway.

卡特兰数求法

就是你当前想求那个数，用for循环乘f(1)f(5)再累加即可

另外声明这题的数用longlong也可以

上代码，很简单

int[] recursion(int n) {

    int[] result = new int[100];

    if (n == 0) {
        result[99] = 1;
        return result;
    }

    if (n == 1) {
        result[99] = 1;
        return result;
    }

    for (int i = 0, j = n - 1; i < n; i ++, j --) {
        result = plus(multi(recursion(i), recursion(j)), result);
    }

    return result;

}

全部代码

public class TrainProblemTwo1023 {

    int[] result;

    TrainProblemTwo1023(int n) {

        result = recursion(n);

    }

    int[] recursion(int n) {

        int[] result = new int[100];

        if (n == 0) {
            result[99] = 1;
            return result;
        }

        if (n == 1) {
            result[99] = 1;
            return result;
        }

        for (int i = 0, j = n - 1; i < n; i ++, j --) {
            result = plus(multi(recursion(i), recursion(j)), result);
        }

        return result;

    }

    void print() {

        for (int i = 0; i < result.length; i ++) {
            if (result[i] == 0) continue;
            System.out.print(result[i] + " ");
        }

    }

    //大数加法 目前只考虑了正数
    int[] plus(int[] a, int[] b) {

        int aLen = a.length;
        int bLen = b.length;

        int maxLen = Math.max(aLen,bLen);
        int cLen = maxLen + 1;//由ab长度得出c长度，考虑到进位

        int c[] = new int[cLen];//注意一开始是倒序的

        int flag = 0;

        if (aLen == bLen) {
            for (int i = aLen - 1, j = 0; i >= 0; i --, j ++) {
                int num = a[i] + b[i] + flag;
                flag = 0;
                if (num >= 10) {
                    num -= 10;
                    flag = 1;
                }
                c[j] = num;
            }

            if (flag == 1) {
                c[cLen - 1] = 1;
            }

        } else {
            int minLen = Math.min(aLen, bLen);
            int k = 0;//这里指代c数组的index

            //加他们共有的部分
            for (int i = aLen - 1, j = bLen -1; i > aLen - 1 - minLen; i --, j --) {

                int num = a[i] + b[j] + flag;
                flag = 0;

                if (num >= 10) {
                    num -= 10;
                    flag = 1;
                }

                c[k] = num;
                k++;

            }

            //不公有的部分
            for (int i = maxLen - minLen - 1; i >= 0; i --) {

                int num = aLen > bLen ? a[i] + flag : b[i] + flag;
                flag = 0;

                if (num >= 10) {
                    num -= 10;
                    flag = 1;
                }

                c[k] = num;
                k ++;

            }

            if (flag == 1) {
                c[cLen - 1] = 1;
            }
        }

        //倒序回来
        //真实位数
        int realLen = cLen;
        //代表没进位
        if (flag == 0) {
            realLen = cLen - 1;
        }
        int temp;
        int d[] = new int[realLen];
        for (int i = 0, j = realLen - 1; i < realLen; i ++, j --) {
            d[i] = c[j];
        }
        return d;
    }

    //大数乘法
    int[] multi(int[] a, int[] b) {

        //乘法可以乘出来的位数 a位数组 * b位数组 最小 a + b - 1位 最大 a + b位
        int aLen = a.length;
        int bLen = b.length;
        int length = aLen + bLen;

        int[] result = new int[length];

        //思路 两个for循环 结果等于每个数之间相乘并且乘以10的（i + j）次，得出这么多结果，累加
        for (int i = 0; i < aLen; i ++) {
            for (int j = 0; j < bLen; j ++) {

                int[] c = new int[length];

                //先给后面的0补补好
                int height = (aLen - i - 1) + (bLen - j - 1);// 5 3

                int sum = a[i] * b[j];
                if (sum >= 10) {
                    c[length - height - 1] = sum % 10;
                    c[length - height - 2] = (sum - sum % 10) / 10;
                } else {
                    c[length - height - 1] = sum;
                }

                result = plus(result, c);
            }
        }

        return result;

    }

    public static void main(final String[] args) throws Exception {

        TrainProblemTwo1023 t = new TrainProblemTwo1023(6);
        t.print();

    }

}