出栈序列的性质及其求解新算法

• 作者: 徐凤生
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: 栈序列 算法 递归
• 年，卷（期）: 2006,（5）
• 所属期刊栏目: 学术探讨
• 页码范围: 66-68,84
• 页数: 4页
• 分类号: TP311
• 字数: 4003字
• 语种: 中文
• DOI: 10.3321/j.issn:1002-8331.2006.05.021

摘要

设集合N={1,2,3,…,n],N中的元素按次序1、2、3、…、n入栈,所有不同的出栈序列的集合记为S[1,2,3,…,n].论文讨论了出栈序列的性质,通过新的计数方法证明了|S[1,2,3,…,n]|=1/n+1(2nn),并给出了求S[1,2,3,…,n]中所有元素的一种新算法.新计数方法与传统的方法相比简单直观,且易于理解.求所有出栈序列的新算法的时间复杂度为O(1/n+1(2nn)),较传统算法速度更快、效率更高.用C语言程序验证了新算法的有效性.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	徐凤生	德州学院计算机系	101	583	13.0	19.0