2011考研考研備考數(shù)據(jù)結(jié)構(gòu)之出棧序列的研究[7]_跨考網(wǎng)
3 判斷一個序列是否為出棧序列
隨著n的變大,出棧序列總數(shù)越來越多,由文獻(xiàn)[1]和[5]可知,出棧序列的求解問題是一個NP問題,所以判斷一個序列是否為一個出棧序列更為重要。在文獻(xiàn)[2]的傳統(tǒng)算法中, 根據(jù)棧的定理[2]判斷某一序列是否為出棧序列,該定理是:對于集合N={1,2,3 ,…,n},如果依次序1,2,3 ,…,n入棧,設(shè)ala2a3…an是1,2,3 ,…,n的一個全排列,則ala2a3…an為出棧序列的充要條件是:對于任意的ai,在它后面的且比它小的數(shù)是降序排列的。由該定理推出結(jié)論: 若p,q,r是入棧序列中的數(shù),且p<q < r,則出序序列中p,q,r的排列次序不可能是r,p,q。?
由上述推論可設(shè)計出判斷某個序列是否為合法的出棧序列,該算法的源代碼如下:?
flag=l; // 沒標(biāo)志為l,假設(shè)序列a為合法的出棧序列
for(u=0;u<=n-2;u++)?
for(v=u+1;v<=n-1;v++)?
for(w=v+l;w<=n;w++)?
if((a[v]<a[w])&&(a[w]<a[u]))flag=0; //若出棧次序為rpq則為不合法的出棧序列
該算法的時間復(fù)雜度為O(n3),算法1采用了該方法判斷某一序列是否為出棧序列,其效率太低,為此文中借助于棧實現(xiàn)復(fù)雜度為O(n)的算法,其基本思想描述如下:?
(1) 初始化棧stack,設(shè)置flag為1;?
(2) v=w=0,v指要判斷的序列,w指入棧的序列;?
(3) 如果v > n或flag=0,則轉(zhuǎn)(9);?
(4) 如果棧stack是空棧,則將第w個入棧序列符號人棧,w++;?
(5) 如果stack棧頂元素值等于序列的第v個元素,或者w ≤ n,則轉(zhuǎn)(7);?
(6) 第w個入棧元素壓入stack棧中,w ++,轉(zhuǎn)(5);?
(7) 如果stack棧頂元素值等于序列的第v個元素,則匹配,stack棧頂元素出棧,v++;否則,說明所判斷的序列不是出棧序列,賦flag為零;?
(8) 轉(zhuǎn)(3);?
(9) 結(jié)束,若此時flag為1,則序列為出棧序列,否則不是。?
將該算法替代算法1中的相應(yīng)部分,稱為改進(jìn)后的算法1。從表1可以看出改進(jìn)后的算法1,在運行時間上比原算法大大縮短,甚至比算法2還要好。
2022考研初復(fù)試已經(jīng)接近尾聲,考研學(xué)子全面進(jìn)入2023屆備考,跨考為23考研的考生準(zhǔn)備了10大課包全程準(zhǔn)備、全年復(fù)習(xí)備考計劃、目標(biāo)院校專業(yè)輔導(dǎo)、全真復(fù)試模擬練習(xí)和全程針對性指導(dǎo);2023考研的小伙伴針也已經(jīng)開始擇校和復(fù)習(xí)了,跨考考研暢學(xué)5.0版本全新升級,無論你在校在家都可以更自如的完成你的考研復(fù)習(xí),暑假集訓(xùn)營帶來了院校專業(yè)初步選擇,明確方向;考研備考全年規(guī)劃,核心知識點入門;個性化制定備考方案,助你贏在起跑線,早出發(fā)一點離成功就更近一點!
點擊右側(cè)咨詢或直接前往了解更多
考研院校專業(yè)選擇和考研復(fù)習(xí)計劃 | |||
2023備考學(xué)習(xí) | 2023線上線下隨時學(xué)習(xí) | 34所自劃線院??佳袕?fù)試分?jǐn)?shù)線匯總 | |
2022考研復(fù)試最全信息整理 | 全國各招生院??佳袕?fù)試分?jǐn)?shù)線匯總 | ||
2023全日制封閉訓(xùn)練 | 全國各招生院校考研調(diào)劑信息匯總 | ||
2023考研先知 | 考研考試科目有哪些? | 如何正確看待考研分?jǐn)?shù)線? | |
不同院校相同專業(yè)如何選擇更適合自己的 | 從就業(yè)說考研如何擇專業(yè)? | ||
手把手教你如何選專業(yè)? | 高校研究生教育各學(xué)科門類排行榜 |
相關(guān)推薦
跨考考研課程
班型 | 定向班型 | 開班時間 | 高定班 | 標(biāo)準(zhǔn)班 | 課程介紹 | 咨詢 |
秋季集訓(xùn) | 沖刺班 | 9.10-12.20 | 168000 | 24800起 | 小班面授+專業(yè)課1對1+專業(yè)課定向輔導(dǎo)+協(xié)議加強課程(高定班)+專屬規(guī)劃答疑(高定班)+精細(xì)化答疑+復(fù)試資源(高定班)+復(fù)試課包(高定班)+復(fù)試指導(dǎo)(高定班)+復(fù)試班主任1v1服務(wù)(高定班)+復(fù)試面授密訓(xùn)(高定班)+復(fù)試1v1(高定班) | |
2023集訓(xùn)暢學(xué) | 非定向(政英班/數(shù)政英班) | 每月20日 | 22800起(協(xié)議班) | 13800起 | 先行階在線課程+基礎(chǔ)階在線課程+強化階在線課程+真題階在線課程+沖刺階在線課程+專業(yè)課針對性一對一課程+班主任全程督學(xué)服務(wù)+全程規(guī)劃體系+全程測試體系+全程精細(xì)化答疑+擇校擇專業(yè)能力定位體系+全年關(guān)鍵環(huán)節(jié)指導(dǎo)體系+初試加強課+初試專屬服務(wù)+復(fù)試全科標(biāo)準(zhǔn)班服務(wù) |