给定- -个足够大的空栈,有4个元素的进栈次序为A、B、 C、D,则以C、D开头的出栈序列的个数为( )。 给定--个足够大的空栈,有4个元素的进栈次序为A、B、C、D,则以C、D开头的出栈序列的个数为()
时间: 2023-12-17 10:04:30 浏览: 46
可以使用卡特兰数求解,设进栈序列为1,2,3,4,则卡特兰数C4为:
C4 = (2*4)! / ((4+1)! * 2^4) = 14
若以C开头,则剩下的三个元素只能以D开头,因为D后面还有两个元素需要弹出,所以剩下的两个元素只有BC和CB两种排列方式,即CDB和CBD。
所以以CD开头的出栈序列的个数为14/4=3。
相关问题
设有A、B、C、D四个元素顺序进栈,在进栈过程可以出栈,出栈次序错误的排列是
四个元素顺序进栈,共有 4! = 24 种出栈次序,其中有且仅有一种是正确的出栈次序。错误的排列包括:
1. A B C D
2. A B D C
3. A C B D
4. A D B C
5. B A C D
6. B A D C
7. B C A D
8. B D A C
9. C A B D
10. C B A D
11. C D A B
12. D A B C
13. D B A C
14. D C B A
正确的出栈次序是:D C B A。
如果进栈序列为A,B,C,D,则可能的出栈序列是
进栈序列为A,B,C,D时,可能的出栈序列有很多种。下面给出一种可能的出栈序列:
D,C,B,A
其它可能的出栈序列包括:
D,C,A,B
D,B,C,A
C,D,B,A
C,B,D,A
C,B,A,D
B,C,D,A
B,D,C,A
B,C,A,D
A,B,C,D
注意,有一些出栈序列是不可能的,比如B,A,C,D或者D,A,B,C,因为在出栈的过程中,某个元素必须在它之前的所有元素都已经出栈了。
相关推荐
![c](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)