//第五届蓝桥杯软件类国赛真题-C-B-2_出栈次序
/*【题目】
标题:出栈次序
X星球特别讲究秩序,所有道路都是单行线。一个甲壳虫车队,共16辆车,
按照编号先后发车,夹在其它车流中,缓缓前行。
路边有个死胡同,只能容一辆车通过,是临时的检查站,如图【p1.png】所示。
X星球太死板,要求每辆路过的车必须进入检查站,也可能不检查就放行,也可能仔细检查。
如果车辆进入检查站和离开的次序可以任意交错。那么,该车队再次上路后,
可能的次序有多少种?
为了方便起见,假设检查站可容纳任意数量的汽车。
显然,如果车队只有1辆车,可能次序1种;2辆车可能次序2种;3辆车可能次序5种。
现在足足有16辆车啊,亲!需要你计算出可能次序的数目。
这是一个整数,请通过浏览器提交答案,不要填写任何多余的内容(比如说明性文字)。
*/
/*【解题思路】
解法一:
我们把n个元素的出栈个数的记为f(n), 那么对于1,2,3, 我们很容易得出:
f(1) = 1 //即 1
f(2) = 2 //即 12、21
f(3) = 5 //即 123、132、213、321、231
然后我们来考虑f(4), 我们给4个元素编号为a,b,c,d, 那么考虑:
元素a只可能出现在1号位置,2号位置,3号位置和4号位置(很容易理解,一共就4个位置,
比如abcd,元素a就在1号位置)。
分析:
1) 如果元素a在1号位置,那么只可能a进栈,马上出栈,此时还剩元素b、c、d等待操作,
就是子问题f(3);
2) 如果元素a在2号位置,那么一定有一个元素比a先出栈,即有f(1)种可能顺序(只能是b),
还剩c、d,即f(2), 根据乘法原理,一共的顺序个数为f(1) * f(2);
3) 如果元素a在3号位置,那么一定有两个元素比1先出栈,即有f(2)种可能顺序(只能是b、c),还剩d,即f(1),
根据乘法原理,一共的顺序个数为f(2) * f(1);
4) 如果元素a在4号位置,那么一定是a先进栈,最后出栈,
那么元素b、c、d的出栈顺序即是此小问题的解,即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)
解法二:
排列公式:C(n,2n)/(n+1) 【其中C(n,2n)表示2n里取n)】
或者C(2n,2n)-C(n-1,2n)
答案:35357670
*/
#include<iostream>
using namespace std;
#define MAX 16+1
int main()
{
int temp;
int a[MAX] = {0};
a[0] = a[1] = 1;
for(int i=2;i < MAX;i++)
{
int j = i;
int sum = 0;
int k = 1;
do
{
sum += a[i-j]*a[i-k];
k++;
}while(--j);
a[i] = sum;
cout<<"f("<<i<<")"<<" = "<<a[i]<<endl;
}
return 0;
}
//#include<iostream>
//using namespace std;
//
///*
// * @简介:获取排列C(m,n)结果 【其中C(m,n)表示从n里取m)】
// * @参数:排列C(m,n)中的m、n值
// * @返回:排列C(m,n)的结果
//*/
//int getCatalanNum(int m,int n)
//{
// int backupM = m;
// int backupN = n;
// int a,b;
// a = n;
// b =m;
// while(--backupM)
// {
// n--;
// a *= n;
// }
//
// while(--m)
// {
// b *= m;
// }
//
// return a/b;
//}
//
//int main()
//{
// cout<<"当有16辆车时,可能的次序种数为:"<<getCatalanNum(16,32)/15;
// return 0;
//}