出棧序列的求解算法
文獻[]給出兩種算法第一種是傳統的解法簡稱算法其實現思想描述如下
) 求…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
[] [] [] [] [] [] [] []
From:http://tw.wingwit.com/Article/program/sjjg/201311/22739.html
