出栈序列的统计

我就是我 2022-08-18 02:23 167阅读 0赞

## 出栈序列的统计 ##

####  ####

##### Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^\_^ #####

## 题目描述 ##

栈是常用的一种数据结构，有n个元素在栈顶端一侧等待进栈，栈顶端另一侧是出栈序列。你已经知道栈的操作有两种：push和pop，前者是将一个元素进栈，后者是将栈顶元素弹出。现在要使用这两种操作，由一个操作序列可以得到一系列的输出序列。请你编程求出对于给定的n，计算并输出由操作数序列1，2，……，n，经过一系列操作可能得到的输出序列总数。

## 输入 ##

一个整数n（1<=n<=15)。

## 输出 ##

一个整数，即可能输出序列的总数目。

## 示例输入 ##

## 示例输出 ##

#include <stdio.h>    
    #include <string.h>    
    #include <math.h>    
    long long int a[21];    
    long long int chan[21];    
    int main()    
    {    
        int i,j,n,m,t,x;    
        long long int s;    
        scanf("%d",&n);    
        memset(a,0,sizeof(a));    
        if(n==1)    
        {    
            printf("1\n");    
        }    
        else if(n==2)    
        {    
            printf("2\n");    
        }    
        else    
        {    
            a[3]=1;    
            a[2]=1;    
            for(i=4; i<=n; i++)    
            {    
                for(j=1; j<=20; j++)    
                {    
                    chan[j]=a[j];    
                }    
                memset(a,0,sizeof(a));    
                for(j=1;j<=20;j++)    
                {    
                    if(chan[j]!=0)    
                    {    
                        t=chan[j];    
                        for(x=j+1;x>=2;x--)    
                        {    
                            a[x]+=t;    
                        }    
                    }    
                }    
            }    
            for(i=1,s=0; i<=20; i++)    
            {    
                s+=i*a[i];    
            }    
            printf("%lld\n",s);    
        }    
        return 0;    
    }