火车出站（栈和队列）

code

6 年前

火车出站（栈和队列）

时间： 1ms 内存：128M

描述：

铁路进行列车调度时, 常把站台设计成栈式结构的站台，试问：

设有编号为1到n的n辆列车, 顺序开入栈式结构的站台, 则可能的出栈序列有多少种?

输入：

4

输出：

14

示例输入：

示例输出：

提示：

参考答案（内存最优[920]）：

#include <stdio.h>
int sum = 0;
void f(int inStack, int wait, int out, int num)
{
    if (out == num)
        sum++;
    else
    {
        if (inStack > 0)
            f(inStack-1, wait, out+1, num);
        if (wait > 0)
            f(inStack+1, wait-1, out, num);
    }
}
int main()
{
	int n;
	scanf("%d",&n);
    f(0, n, 0, n);
    printf ("%d\n", sum);
	return 0;
}

参考答案（时间最优[0]）：

#include <iostream>
#define N 40
using namespace std;
long long c[40];
void clante()
{
    int i;
    c[0]=c[1]=1;
    for(i=2;i<=N;i++)
        c[i]=c[i-1]*(4*i-2)/(i+1);
}
int main()
{
    int n;
    clante();
    while(cin>>n)
    {
        cout<<c[n]<<endl;
    }
    return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。