SDUT 1266 出栈序列统计


 
 
题目描述
栈是常用的一种数据结构，有n个元素在栈顶端一侧等待进栈，栈顶端另一侧是出栈序列。你已经知道栈的操作有两种：push和pop，前者是将一个元素进栈，后者是将栈顶元素弹出。现在要使用这两种操作，由一个操作序列可以得到一系列的输出序列。请你编程求出对于给定的n，计算并输出由操作数序列1，2，……，n，经过一系列操作可能得到的输出序列总数。
输入
一个整数n（1<=n<=15)。
输出
一个整数，即可能输出序列的总数目。
示例输入
3
示例输出
5
这是我们oj的一道题目，昨天哥几个在宿舍中说道今天讲栈，出几个题目，偶尔看到这个题了，自己没有做过，就想着做一做，一开始还真是没有思路，无奈之余就在纸上画了画，才慢慢的懂得。有规律的
 
[cpp] 
#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;  
}

补充：软件开发 , C++ ,