文章目录
问题描述
前几天看到一个题目，假设五个元素的入栈顺序为e1、e2、e3、e4、e5，那么共有多少种出栈顺序？一时之间思路全无，现在把它整理一下。
对栈的理解
栈是一种运算受到限制的线性表，这种限制具体表现在只能在栈的一端进行插入和删除，这一端为栈顶，另一端即为栈底。
向一个栈中插入新的元素被称为入栈、进栈或压栈，新加入的元素被放在栈顶，成为新的栈顶元素；从一个栈中删除一个元素称为出栈或退栈，是将处于栈顶的元素从栈中删除，与其相邻的元素成为新的栈顶元素。—-《百度百科》
栈的一个特点就是先进先出，只对栈顶元素进行操作。
题目的思考
题目中让求出5个元素共有多少种出栈顺序，那么是不是可以从只有1个元素时开始开始？
当只有e1存在时，只可能出现1种情况，即e1入栈，e1出栈
当e1、e2按照顺序入栈时，会有2种可能情况：
- e1入栈、e2入栈、e2出栈、e1出栈，即 21
- e1入栈、e1出栈、e2入栈、e2出栈 ，即12
当e1、e2、e3按照顺序入栈时，会有5种可能情况：
- e1入栈、e2入栈、e3入栈、e3出栈、e2出栈、e1出栈，即321
- e1入栈、e2入栈、e2出栈、e3入栈、e3出栈、e1出栈，即231
- e1入栈、e2入栈、e2出栈、e1出栈、e3入栈、e3出栈，即213
- e1入栈、e1出栈、e2入栈、e3入栈、e3出栈、e2出栈，即132
- e1入栈、e1出栈、e2入栈、e2出栈、e3入栈、e3出栈，即123
当e1、e2、e3、e4按照顺序入栈时，这种暴力列举方法很难使用了，可以这样考虑：元素e1可能会第一个出栈，也可能最后一个出栈，那么根据e1出栈的位次，总共会有四种情况：
- e1第一个出栈，那么只可能是e1进栈之后马上出栈，那么剩下的e2、e3、e4可以划分为三个元素的出栈问题；
- e1第二个出栈，那么一定有一个元素在e1之前出栈，根据栈的性质，这个元素只可能是e2，那么剩下的两个元素e3、e4可以划分为两个元素的出栈问题；
- e1第三个出栈，那么一定有两个元素在e1之前出栈，这两个元素为e2、e3，那么剩下可以划分为两个元素的出栈问题，在e1之后出栈的元素为e4；
- e1第四个出栈，那么前三个出栈的元素可以划分为三个元素的出栈问题
为了方便寻找规律，我们把n个元素的出栈顺序次数f(n)，记f(0)=1,有f(1)=1，f(2)=2，f(3)=5，那么可以得到 ：f(4)=f(0)×f(3)+f(1)×f(2)+f(2)×f(1)+f(3)×f(0)
推广到n个元素的时候，就是：
即
代码如下（自己写的，技术低微多多包涵）：
def check_int(x):
try:
int(x)
return True
except ValueError:
return False
def function(x):
sum = 0
if x == 0:
return 1;
if x == 1:
return 1;
if x == 2:
return 2;
if x == 3:
return 5;
else:
for i in range(0,x):
count = function(i) * function(x-i-1)
sum = sum +count
return sum
if __name__ == '__main__':
n = input()
if check_int(n) == True:
n = int(n)
y = function(n)
print(y)
if check_int(n) == False:
print("输入错误")
卡特兰数
刚才的过程一个递推公式，时间复杂度为O(n^2)，那么怎样做才可以降低他的时间复杂度？其实这个递推公式就是卡特兰数，他还有另外的通项公式：
具体的卡特兰数介绍过程：
卡特兰数的代码实现就很简单了
def catalan(n):
if n==0 or n==1:
return 1
return int(((4 * n-2) * catalan(n-1)) / (n+1))
i = int(input())
print(catalan(i))
扩展思路
输出所有的出栈顺序
生成所有的出栈序列 （回溯法）——python
s = input().split(',')
class Solution:
def __init__(self, s):
self.s = s
self.n = len(s)
self.result = []
def all_unstack(self, i, stack, seq):
if i == self.n:
if stack:
top = stack.pop()
seq.append(top)
self.all_unstack(i, stack, seq)
stack.append(top)
seq.pop()
else:
self.result.append(''.join(seq))
else:
stack.append(self.s[i])
self.all_unstack(i + 1, stack, seq)
stack.pop()
if stack:
top = stack.pop()
seq.append(top)
self.all_unstack(i, stack, seq)
seq.pop()
stack.append(top)
def print_all_sequence(self):
for each in self.result[::-1]:
print(each)
solution = Solution(s)
solution.all_unstack(0, [], [])
solution.print_all_sequence()
引用：
https://blog.csdn.net/weixin_39441762/article/details/106438966
https://blog.csdn.net/hanyue0102/article/details/81428693
https://blog.csdn.net/hecongqing/article/details/52833102?spm=1001.2101.3001.6650.1&utm_medium=distribute.pc_relevant.none-task-blog-2%7Edefault%7ECTRLIST%7ERate-1.pc_relevant_default&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2%7Edefault%7ECTRLIST%7ERate-1.pc_relevant_default&utm_relevant_index=2Original: https://blog.csdn.net/weixin_44561567/article/details/123829880
Author: 日思夜酒。
Title: 元素入栈顺序确定，共有多少种出栈顺序？—-Python
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/758822/
转载文章受原作者版权保护。转载请注明原作者出处！