一个栈的输入序列是12345,则输出序列有多少种,这类题型有什么规律?

来源：学生作业帮编辑：搜搜做题作业网作业帮分类：数学作业时间：2024/04/30 19:09:30

可以把这个问题描述为一个二元组表示进栈出栈的状态,(n, 0) 表示有n个元素等待进栈, 0 个元素已进栈,
这相当于问题最初的状况. 接着问题转化为(n-1,1).
可以这么说(n,0) = (n-1,1). 而对于(n-1,1)则相当于(n-1,0)+(n-2,2).
其中(n-1,0)表示栈中的一个元素出栈, (n-2, 2)表示又有一个元素入栈.也就是说,对于(n-1,1),已经有1个进栈的情况,这时候有两种可能：①把栈里面的这个元素出掉,②继续把一个元素进栈,这两种选择导致的序列是不同的,这个是理解的难点和关键点.
这样我们得到了转化公式,把问题一般化,则(n,m)的排列问题可以转化为(n,m-1)+(n-1,m+1)
此时m>=1, 因为必须栈中有元素才可以出栈.
当m=0则(n,0)的问题只能转化为(n-1,1).
当问题为(0, m)时得到递归边界,这个问题的解是只有一种排列.
最终推导的结果是：P2n ＝ C（n 2n）— C（n＋1 2n）=C（n 2n)/(n+1)

这个结果是一个“卡塔兰数”Catalan,在组合数学中有介绍,可以参阅有关资料.

结果=C(5,10)/6= 42

3个元素的情况参考下这个输入ABC的例子,可能比较直观.

一个栈的输入序列是12345,则输出序列有多少种,这类题型有什么规律? 若一个栈的输入序列为1,2,3,…,n,输出序列的第一个元素是i,则第j个输出元素是_____. ( )3.设一个栈的输入序列为A,B,C,D,则借助一个栈所得到的输出序列不可能是_______. 一个空栈,输入序列ABCDE经过push push pop push pop后输出序列为排列组合问题证明有n个数在输入序列中,其中j个是不相同的.按顺序输出到输出序列,每次输出的时候都和输出序列中的每一个数字蛋白质的基因序列和氨基酸序列有什么区别? 一个栈的入栈序列为A B C D E 则不可能的输出序列为 C编程：已有一个排好序的序列,输入一个数插入该序列中,使其仍然保持有序.（用数组知识解决. 求数字电路高手用D触发器设计一个Mealy型的同步时序逻辑电路,该电路有一个输入端X和一个输出端Z,当串行输入序列出现1 基因序列和碱基序列有什么不同氨基酸序列与蛋白质序列有什么区别啊? 时期序列和时点序列有什么区别?