|
出栈序列的求解算法 文献[]给出两种算法第一种是传统的解法简称算法其实现思想描述如下 ) 求…n的一个全排列alaa…an ) 判断alaa…an是否为出栈序列若是则输出 ) 若所有全排列已求出则结束否则转() 该算法时间复杂度为O(n!) 文献[]给出的第二种算法简称算法实现思想描述如下 () 若n=则写下唯一的出栈序列 () 递归调用该算法求出作为第k个出栈元素的所有出栈序列 该算法时间复杂度是O(C(nn)／(+n) )但该算法在实现时对产生的每一个出栈序列都要与已有的出栈序列进行对比看是否重复然后决定是否将新的出栈序列加入到已有的出栈序列中这种查找工作使程序的实际运行时间增长 文献[]给出一种更好的算法简称算法具体算法描述如下 ① 若n=则写下唯一的栈排列 ② 否则递归调用该算法生成…n的所有不同的栈排列然后生成…n的所有不同的栈排列方法是对于…n 的每一个栈排列分别将n插入n之前n之后使n与n相邻以及排在n后的每一个数之后即可得到…n的栈排列 该算法利用了栈的性质[]已知集合N={…n}如果按给定的次序…n依次入栈 则在出栈序列中对于任何i ∈N和j∈N( j > i ) 若排在i之前(i左边)要么j与i相邻 要么j与i之间所排的任一数均大于i [] [] [] [] [] [] [] [] |
