加载中…入栈顺序为abcdef,求出栈顺序有多少种
(2011-09-15 12:12:08)| 分类： DataStructure |
必须要选第一个入栈元素为参考元素。
f[i] = sum[i-1]
* sum[n-i];//f(i)：当第一个入栈元素第i个出栈
sum[n]+=f[i];
int count;
cin>>count;
int
sum[count+1],f[count+1];
sum[0] = 1;
sum[1] = 1;
for(int i =
2;i<=count;i++)
{
sum[i] =
0;
}
for(int
j=2;j<=count;j++)
{
for(int i=1;i<=j;i++)
{
f[i] =
sum[i-1]*sum[j-i];
sum[j]+=
f[i];
}
}
cout<<sum[count]<<endl;
system("pause");
return 0;
因为假如第i个入栈元素是在第i个前出栈，则会对它前面的元素产生限制。如入栈顺序为123，若3第一个出栈，则后面只能是21的顺序，即321。
所以选第一个入栈元素为参考元素，无论将它放到哪个位置，都不会对其他元素产生影响。
故公式为：
int sum[n] = 0;//n个数的出栈顺序总和
for(int i=1;i<=n;i++)
{
}
其中，f(i)的含义是当第一个入栈元素第i个出栈时，有多少种出栈方法。如1，2，3，4入栈,f(2)为1第二个出栈，等于sum[1]
* sum[2]；即为前(i-1)个有多少种出栈顺序 * 后(i-n)个与多少种出栈顺序。
最后，将第一个元素在各个位置的种类累加，就得到n个数的出栈顺序总和。
代码如下：
#include<iostream>
using namespace std;
#include<cstdlib>
int main()
{
}
喜欢
0
赠金笔