問(wèn)題描述
棧是常用的一種數(shù)據(jù)結(jié)構(gòu)挂据，有n個(gè)元素在棧頂端一側(cè)等待進(jìn)棧，棧頂端另一側(cè)是出棧序列儿普。你已經(jīng)知道棧的操作有兩種：push和pop崎逃，前者是將一個(gè)元素進(jìn)棧，后者是將棧頂元素彈出∶己ⅲ現(xiàn)在要使用這兩種操作个绍，由一個(gè)操作序列可以得到一系列的輸出序列勒葱。請(qǐng)你編程求出對(duì)于給定的n，計(jì)算并輸出由操作數(shù)序列1巴柿，2凛虽，…，n广恢，經(jīng)過(guò)一系列操作可能得到的輸出序列總數(shù)凯旋。
輸入
就一個(gè)數(shù)n(1≤n≤15)。
輸出
一個(gè)數(shù)钉迷，即可能輸出序列的總數(shù)目至非。
樣例輸入
3
樣例輸出
5
問(wèn)題分析
常規(guī)分析（循環(huán)遞歸）
首先設(shè)f(n)為序列個(gè)數(shù)為n的出棧順序序列數(shù)，先假定最后出來(lái)的元素為k,則在k入棧前有f(k-1)種情況糠聪，在k出棧前有f(n-k)種情況荒椭，由于前k-1項(xiàng)與后n-k項(xiàng)相互獨(dú)立，則用乘法定理可得最后出來(lái)的元素為k的情況有f(k-1)f(n-k)種枷颊；而k可以從1~n戳杀，所以f(n)=f(0)f(n-1)+f(1)f(n-2)...+f(n-1)f(0)；
源代碼
#include<stdio.h>
int f(int n)
{
int sum=0;
if(n==0||n==1) return 1;
else{
for (int i=1;i<=n;i++)
{
sum+=f(i-1)*f(n-i);
}
}
return sum;
}
int main()
{
int n;
scanf("%d",&n);
printf("%d",f(n));
}
