1069 - 火车出站
时间限制 : 1 秒
内存限制 : 32 MB
铁路进行列车调度时,常把站台设计成栈式结构的站台,试问:
设有编号为1到n的n辆列车,顺序开入栈式结构的站台,则可能的出栈序列有多少种?
题目输入
输入包含多组测试数据。每组为一个正整数n(1<=n<=20),表示有n辆列车。
题目输出
输出可能的出栈序列有多少种。
输入/输出样例
输入格式
4 3
输出格式
14 5
C语言解答
#include<stdio.h> double f(int n) { int i; double a=1; for(i=1;i<=n;i++) a=a*i; return a; } void main() { int n; while(scanf("%d",&n)==1) { printf("%.lf\n",f(2*n)/(f(n)*f(n)*(n+1))); } }
C++解答
#include <iostream> #include <cstring> using namespace std; long long f[25][25]; int main(){ int n; while (cin>>n){ memset(f,0,sizeof(f)); for (int i=1;i<=n;i++) f[i][0]=1; for (int i=1;i<=n;i++){ for (int j=1;j<=i-1;j++) f[i][j]=f[i-1][j]+f[i][j-1]; f[i][i]=f[i][i-1]; } cout<<f[n][n]<<endl; } return 0; }
Java解答
import java.util.*; import java.math.*; public class Main{ public static void main(String[] args){ Scanner in = new Scanner(System.in); while(in.hasNextInt()){ int n = in.nextInt(); int i = n; int j = n*2; BigInteger up = BigInteger.valueOf(i); BigInteger down = BigInteger.valueOf(j); BigInteger a = BigInteger.valueOf(0); for(int k = i, l = 1;l<i;k--,l++) up = up.multiply(BigInteger.valueOf(k - 1)); for(int k = j, l = 1;l<i;k--,l++) down = down.multiply(BigInteger.valueOf(k - 1)); a = down.divide(up).divide(BigInteger.valueOf(n+1)); System.out.println(a); } } }