C语言编程练习38：火车出站

题目描述

铁路进行列车调度时，常把站台设计成栈式结构的站台，试问：
设有编号为1到n的n辆列车，顺序开入栈式结构的站台，则可能的出栈序列有多少种？

输入

输入包含多组测试数据。每组为一个正整数n（1<=n<=20），表示有n辆列车。

输出

输出可能的出栈序列有多少种。

样例输入 Copy

4
3

样例输出 Copy

14
5


思路：一开始用全排列函数，判断每个序列是否是合法的出栈序列，但是超时了。所以直接卡塔兰数计算公式
　　　　　　(2*n)！ / (n！ *(n + 1)！) （其中n>=1）
但是要优化一下，因为可能溢出，不用int用longlong

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;


int main()
{
   int n;

   while(cin >> n)
   {
       long long s=1;
       for(int i=1;i<=n;i++)
       {
           s=s*(n+i)/i;
       }
       cout << s/(n+1) << endl;
   }
    return 0;
}