火车出站(栈和队列)

火车出站(栈和队列)

时间: 1ms        内存:128M

描述:

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

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

输入:

4

输出:

14

示例输入:

3

示例输出:

5

提示:

参考答案(内存最优[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;
}

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

点赞