摘要
设集合N={1,2,3,…,n},N中的元素按次序1、2、3、…、n入栈,所有不同的出栈序列的集合记为S[1,2,3,…,n]。论文讨论了出栈序列的性质,通过新的计数方法证明了|S[1,2,3,…,n]|=n+112n!"n,并给出了求S[1,2,3,…,n]中所有元素的一种新算法。新计数方法与传统的方法相比简单直观,且易于理解。求所有出栈序列的新算法的时间复杂度为O(n+112n!"n),较传统算法速度更快、效率更高。用C语言程序验证了新算法的有效性。
Let set N={1,2, …,n},its elements is been put in the stack in order 1,2,…,n,all of different coming out stack sequence set is S[1,2,3,…,n].Properties of coming out stack sequence is discussed,|S[1,2,3,… ,n]|=1/n+1(n^2n) is proved by new computing number method,and a new algorithm for finding all coming out stack sequenee is put forward in this paper.New computing number method is more simply and easy understanding than traditional ones,time complexity of new algorithm for finding all coming out stack sequence is O (1/n+1(n^2n)), with higher efficiency than traditional ones.The validity of algorithm is proved by C programme.
出处
《计算机工程与应用》
CSCD
北大核心
2006年第5期66-68,84,共4页
Computer Engineering and Applications
基金
德州市科学技术攻关计划资助项目(编号:040705)
关键词
栈序列
算法
递归
stack numbers, algorithm, recursion