n个元素顺序进栈，那么出栈的顺序有多少种？

本文主要是介绍n个元素顺序进栈，那么出栈的顺序有多少种？，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

我们把n个元素的出栈个数的记为f(n), 那么对于1,2,3, 我们很容易得出：

　　f(1) = 1
　　f(2) = 2
　　f(3) = 5
　　然后我们来考虑f(4), 我们给4个元素编号为1,2,3,4, 那么考虑：元素1出栈顺序可能出现在1号位置，2号位置，3号位置和4号位置(很容易理解，一共就4个位置，比如1234,元素1就在1号位置)。
　　分析：
　　1) 如果元素1在1号位置，那么只可能1进栈，马上出栈，此时还剩元素2、3、4等待操作，就是子问题f(3)；
　　2) 如果元素1在2号位置，那么一定有一个元素比1先出栈，即有f(1)种可能顺序（只能是2），还剩3、4，即f(2)，     根据排列组合，一共的顺序个数为f(1) * f(2)；
　　3) 如果元素1在3号位置，那么一定有两个元素比1先出栈，即有f(2)种可能顺序（只能是2、3），还剩4，即f(1)，
　　根据排列组合，一共的顺序个数为f(2) * f(1)；
　　4) 如果元素1在4号位置，那么一定是1先进站，最后出栈，那么元素2、3、4的出栈顺序即是此小问题的解，即         f(3)；
　　结合所有情况，即f(4) = f(3) + f(2) * f(1) + f(1) * f(2) + f(3);
　　为了规整化，我们定义f(0) = 1；于是f(4)可以重新写为：
　　f(4) = f(0)*f(3) + f(1)*f(2) + f(2) * f(1) + f(3)*f(0)
　　然后我们推广到n，推广思路和n=4时完全一样，于是我们可以得到：
　　f(n) = f(0)*f(n-1) + f(1)*f(n-2) + ... + f(n-1)*f(0)
　　即
　　
F[n]=∑(i=0,i<=n-1)F[i]*F[n-i](显然初始条件为F[0]=1,F[1]=1）
n个元素的情况可分为三个阶段，先进i个元素入栈出栈（有F[i]种情况），然后第i+1个元素直接入栈出栈，再n-（i+1）个元素入栈出栈（F[n-i-1]种情况），所以是F[i]*F[n-i-1]种情况，显然i的取值范围是[0,n-1]，累加即是结果。

这个的结果有数学公式的 是C(n,2n)-C(n-1,2n),至于公式怎么来,必须将问题转化为数学问题“卡塔兰数”(Catalan).程序员的做法是用递归,要想写出效率高的程序,就得用这个数学问题推导出来的公式.
　
#include <iostream>
#include<cstring>
using namespace std;
int popnumber(int num)
{
	int sum=0;
	if (num == 0 || num == 1)
		return 1;
	else if (num == 2)
		return 2;
	for (int i = 0; i < num; i++)
	{
		sum += popnumber(i)*popnumber(num-1-i);
	}
	return sum;
}
int main(int argc, char** argv)
{
	int len;
//	string str;
//	cout<<"输入入栈的元素："
// cin>>str;
// len=str.length(); 
cout<<"输入入栈元素个数："; 
cin>>len;	 
cout<<"出栈可能结果为："<<popnumber(len)<<endl;
return 0;
}