一个栈的输入序列是12345,则输出序列有多少种,这类题型有什么规律?
来源:学生作业帮助网 编辑:作业帮 时间:2024/07/04 21:40:34
![一个栈的输入序列是12345,则输出序列有多少种,这类题型有什么规律?](/uploads/image/z/2479238-62-8.jpg?t=%E4%B8%80%E4%B8%AA%E6%A0%88%E7%9A%84%E8%BE%93%E5%85%A5%E5%BA%8F%E5%88%97%E6%98%AF12345%2C%E5%88%99%E8%BE%93%E5%87%BA%E5%BA%8F%E5%88%97%E6%9C%89%E5%A4%9A%E5%B0%91%E7%A7%8D%2C%E8%BF%99%E7%B1%BB%E9%A2%98%E5%9E%8B%E6%9C%89%E4%BB%80%E4%B9%88%E8%A7%84%E5%BE%8B%3F)
一个栈的输入序列是12345,则输出序列有多少种,这类题型有什么规律?
一个栈的输入序列是12345,则输出序列有多少种,这类题型有什么规律?
一个栈的输入序列是12345,则输出序列有多少种,这类题型有什么规律?
可以把这个问题描述为一个二元组表示进栈出栈的状态,(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的例子,可能比较直观.