1069 - 火车出站

通过次数

0

提交次数

0

时间限制 : 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);
    }
}
}