1330: 出栈序列统计卡特兰数

怼烎@ 2024-02-18 22:29 58阅读 0赞

## [出栈顺序（卡特兰数）][Link 1] ##

题目描述：

按照1,2,...,n-1,n的顺序入栈，问可以得到多少种出栈序列。如n=3时有1 2 3，1 3 2，2 1 3，2 3 1，3 2 1共5种出栈序列。

解题思路：

设f（n）为n个数时的方案数。

可知 f（0）=1； f（1）=1； f（2）=2； f（3）=5；

当n=4时 ：

F1 F2 F3 F4

1　　2　　3　　4 //四种状态分别标记为F1，F2，F3，F4

若F1 位于一号位置 则之前的数字出栈顺序的情况数为F(0),在一号位置后的数字出栈顺序的情况数为f（3）;

则F1 位于一号位置时方案总数为f（0）\*f（3）；

若F1 位于二号位置 则F1之前的位置的数字出栈顺序的情况数可知为f(1)，在二号位置之后的数字的出栈顺序为f（2）。

则F1位于二号位置时方案总数为f（1）\*f（2）；

同理：F1位于三号位置时 方案数为 f（2）\*f（1）；

F1位于四号位置时 方案数为f（3）\*f（0）；

由上述条件可以推出：

f（4）=f（0）\*f（3）+f（1）\*f（2）+f（2）\*f（1）+f（3）\*f（0）；

则当n未知时由以上结论可推：

f(n)=f(0)\*f(n-1)+f(1)\*f(n-2)+f(2)\*f(n-3)......f(n-2)\*f(1)+f(n-1)\*f(0);

以上就是本题的一般递推式，我们会发现 这个式子的实际时间复杂度为O（n^2）;

当然不是很快，于是我们引入 卡特兰数；

所谓卡特兰数 就是 当递推式中出现 **h(n)= h(0)\*h(n-1)+h(1)\*h(n-2) + ... + h(n-1)h(0) (n>=2)** 时，

可知代数式的解为　　　　　　　　**h(n)=C(2n,n)/(n+1) (n=0,1,2,...)；**

它的另类递推式为 　　　　　　　**h(n)=h(n-1)\*(4\*n-2)/(n+1);　　　　//本人数学弱渣 具体怎么推导请找百度君**

于是乎我们的式子就化简为了 f（n）=f(n-1)\*(4\*n-2)/(n+1)

**①****对于出栈序列中的每一个数字，在它后面的、比它小的所有数字，一定是按递减顺序排列的。**

比如入栈顺序为：1 2 3 4。

出栈顺序：4 3 2 1是合法的，对于数字 4 而言，比它小的后面的数字是：3 2 1，且这个顺序是递减顺序。同样地，对于数字 3 而言，比它小的后面的数字是： 2 1，且这个顺序是递减的。....

出栈顺序：1 2 3 4 也是合法的，对于数字 1 而言，它后面没有比它更小的数字。同样地，对于数字 2 而言，它后面也没有比它更小的数字。

出栈顺序：3 2 4 1 也是合法的，对于数字 3 而言，它后面比 3 小的数字有： 2 1，这个顺序是递减的；对于数字 2 而言，它后面的比它 小的数字只有 1，也算符合递减顺序；对于数字 4 而言，它后面的比它小的数字也只有1，因此也符合递减顺序。

出栈顺序：3 1 4 2 是**不合法**的，因为对于数字 3 而言，**在3后面的比3小的数字有：1 2，这个顺序是一个递增的顺序(1-->2)。**

**因此，当给定一个序列时，通过这个规律 可以轻松地判断 哪些序列是合法的，哪些序列是非法的。**

**②给定一个入栈顺序：1 2 3 .... n，一共有多少种合法的出栈顺序？参考：[百度百科卡特兰数][Link 2]**

答案是 卡特兰数。即一共有：h(n)=c(2n,n)/(n+1) 种合法的出栈顺序。

如果仅仅只需要求出一共有多少种合法的出栈顺序，其实就是求出组合 C(2n,n)就可以了。而求解C(2n,n)，则可以用动态规划来求解

###  ###

### **1330: 出栈序列统计** ###

时间限制: 1 Sec 内存限制: 128 MB  
提交: 53 解决: 43  
您该题的状态：**已完成**  
\[[提交][Link 3]\]\[[状态][Link 4]\]\[[讨论版][Link 5]\]

### **题目描述** ###

栈是常用的一种数据结构，有n个元素在栈顶端一侧等待进栈，栈顶端另一侧是出栈序列。你已经知道栈的操作有两种：push和pop，前者是将一个元素进栈，后者是将栈顶元素弹出。现在要使用这两种操作，由一个操作序列可以得到一系列的输出序列。请你编程求出对于给定的n，计算并输出由操作数序列1，2，…，n，经过一系列操作可能得到的输出序列总数。

### **输入** ###

一个整数n（1<=n<=15）

### **输出** ###

一个整数，即可能输出序列的总数目。

### **样例输入** ###

3

### **样例输出** ###

5

### **提示** ###

先了解栈的两种基本操作，进栈push就是将元素放入栈顶，栈顶指针上移一位，等待进栈队列也上移一位，出栈pop是将栈顶元素弹出，同时栈顶指针下移一位。  
  
用一个过程采模拟进出栈的过程，可以通过循环加递归来实现回溯：重复这样的过程，如果可以进栈则进一个元素，如果可以出栈则出一个元素。就这样一个一个地试探下去，当出栈元素个数达到n时就计数一次(这也是递归调用结束的条件)。

### **来源** ###

[数据结构][Link 6]

这道题，我刚开始还想着，玩个递归，没想到程序崩溃，玩不起，后来，有人提醒用卡特兰数，我一搜，数学好的，就是不一样。

\#include<iostream> 
\#include<stdlib.h> 
using namespace std; 
int main() 
\{ 
int n,i,j; 
long long a\[20\]=\{1,1,2,5\}; 
for(i=4;i<20;i++) 
a\[i\]=a\[i-1\]\*(4\*i-2)/(i+1); 
cin>>n; 
printf("%lld\\n",a\[n\]); 
return 0; 
\}

[Link 1]: https://www.cnblogs.com/PengGG/p/4789929.html
[Link 2]: http://baike.baidu.com/view/2499752.htm
[Link 3]: http://xyoj.xynu.edu.cn/submitpage.php?id=1330
[Link 4]: http://xyoj.xynu.edu.cn/problemstatus.php?id=1330
[Link 5]: http://xyoj.xynu.edu.cn/bbs.php?pid=1330
[Link 6]: http://xyoj.xynu.edu.cn/problemset.php?search=%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84