最長公共子序列問題(共21頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上目 錄1 前言若給定序列X=x1,x2,xm，則另一序列Z=z1,z2,zk，是X的子序列是指存在一個嚴(yán)格遞增下標(biāo)序列i1,i2,ik使得對于所有j=1,2,k有：zj=xij。例如，序列Z=B，C，D，B是序列X=A，B，C，B，D，A，B的子序列，相應(yīng)的遞增下標(biāo)序列為2，3，5，7。給定2個序列X和Y，當(dāng)另一序列Z既是X的子序列又是Y的子序列時，稱Z是序列X和Y的公共子序列。請使用C語言編程，設(shè)計一個有效的算法解決下述問題：給定2個序列X=x1,x2,xm和Y=y1,y2,yn，找出X和Y的最長公共子序列。2 需求分析2.1 任務(wù)和要求使用C語言編程，設(shè)計一個有效

2、的算法解決下述問題：給定2個序列X=x1,x2,xm和Y=y1,y2,yn，找出X和Y的最長公共子序列。2.2 運(yùn)行環(huán)境（1）WINDOWS2000/XP系統(tǒng)（2）Visual C+ 6.0編譯環(huán)境或TC編譯環(huán)境2.3 開發(fā)工具C語言3 分析和設(shè)計3.1 系統(tǒng)分析及設(shè)計思路設(shè)序列X=x1,x2,xm和Y=y1,y2,yn的最長公共子序列為Z=z1,z2,zk ，則(1)若xm=yn，則zk=xm=yn，且zk-1是xm-1和yn-1的最長公共子序列。(2)若xmyn且zkxm，則Z是xm-1和Y的最長公共子序列。(3)若xmyn且zkyn，則Z是X和yn-1的最長公共子序列。由此可見，2個序列

3、的最長公共子序列包含了這2個序列的前綴的最長公共子序列。由最長公共子序列問題的最優(yōu)子結(jié)構(gòu)性質(zhì)建立子問題最優(yōu)值的遞歸關(guān)系。用cij記錄序列和的最長公共子序列的長度。其中， Xi=x1,x2,xi；Yj=y1,y2,yj。當(dāng)i=0或j=0時，空序列是Xi和Yj的最長公共子序列。故此時Cij=0。程序的設(shè)計思路是：調(diào)用函數(shù)void Initialize（），輸入兩個字符串，對兩個串的存儲數(shù)組b，c進(jìn)行動態(tài)分配。調(diào)用函數(shù)void LCSLength（int m,int n,string x,string y,int*c,int*b），將長度較小的字符串作為第一參數(shù)，將長度較大的字符串作為第二個參數(shù)。調(diào)

4、用函數(shù)void LCS（inti，int j,string x,int*b）構(gòu)造最長公共子序列調(diào)用函數(shù)。調(diào)用函數(shù)ReadCommand進(jìn)行系統(tǒng)操作屏幕指示，然后利用函數(shù)void Interpret（char&cmd）對函數(shù)進(jìn)行總體操作，最后得出最長公共子序列。3.2 主要數(shù)據(jù)結(jié)構(gòu)及算法動態(tài)申請兩個字符串的存儲空間:using namespace std;string x,y系統(tǒng)操作屏幕指示: ReadCommand(cmd)字符串比較函數(shù):void LCSLength（int m,int n,string x,string y,int*c,int*b）構(gòu)造最長公共子序列調(diào)用函數(shù):voi

5、d LCS（inti，int j,string x,int*b）動態(tài)申請兩個字符串的存儲空間:using namespace std;string x,y3.3 函數(shù)流程圖Realese()/釋放指針boarci=newtn+1;bi=new intn+1;int i=0;i<=m;i+m=x.length();n=y.length();c=new int*m+1;b=new intm+1;開始 using namespace stdstringx,y;int*c,*b,m,n;char cmd;ReadCommand(cmd);Interpret(cmd);cmd!=q&&am

6、p;cmd!=Q N Yreturn 0ReadCommand(char&cmd) cout<<“nnt請選擇操作： ”；cin>>cmd;cout<<cmd!=c&&cmd!C&&cmd!=q&&cmd!=Q); N Y Initialize（）m=x.length();n=y.length();c=new int*m+1;b=new intm+1; int i=0;i<=m;i+ N Y Realese()/釋放指針boardci=newtn+1;bi=new intn+1;delete ci

7、;delete bi;deletec;deleteb;interpret(char&cmd)switch(cmd)casec:caseC;Initialize();LCSLength(m,n,x,y,c,b);Display();Realese();break;LCSLength(int m,int n,string x,string y,int*c,int*bint i=0；i<=m;i+ N Yxi-1=yj-1cij=ci-1j-1+1;bij=1;ci-1j>=ij-1cij=ci-1j;bij=2;(i=0;i<=m;i+)ci0=0;(i=1;i<=

8、n;i+)c0i=0;i=1;i<=m;i+;j=1;j<=n;j+; N Y N Y N YLCS(int i,int j,string x,int *b)i=0|j=0cij=cij-1;bij=3return bij=1 N Y N Ybij=2LCS(i-1,j,x,b)LCS(I,j-1,x,b)Dispiay()結(jié)束LCS(i-1,j-1,x,b);count<<xi-1;圖3.1 程序總體流程圖流程圖4 具體代碼實(shí)現(xiàn)#include<iostream>#include<string>using namespace std;strin

9、g x,y;/x,y用來存放字符序列int *c,*b,m,n;/*m，n分別存儲字符串x,y的長度,數(shù)組cij存儲Xi和Yj得最長公共子序列的長度，bij記錄cij的值是有哪一個子問題的解得到的*/void LCSLength(int m,int n,string x,string y,int *c,int*b);void LCS(int i,int j,string x,int *b);void Initialize();/對數(shù)組b,c動態(tài)分配空間以及對其進(jìn)行初始化void ReadCommand(char &cmd);void Interpret(char &cmd);v

10、oid Realese();/釋放指針void Display();int main()char cmd;doReadCommand(cmd);Interpret(cmd);while(cmd!='q'&&cmd!='Q');return 0;void ReadCommand(char &cmd)system("cls"); /清屏cout<<"n-n"cout<<"ntttt操 作 提 示"cout<<"n-n"cout&

11、lt;<"tquit-q/Q tt continue-c/Cn"docout<<"nnt請選擇操作："cin>>cmd;cout<<"n-n"while(cmd!='c'&&cmd!='C'&&cmd!='q'&&cmd!='Q');void Initialize()cout<<"分別輸入兩個字符串（每個字符串以回車結(jié)束）n"cin>>x;

12、cin>>y;m=x.length();n=y.length();c=new int*m+1;b=new int*m+1;for(int i=0;i<=m;i+)ci=new intn+1;bi=new intn+1; void Realese()/釋放指針boardfor(int i=0;i<=m;i+)delete ci;delete bi;delete c;delete b;void Interpret(char &cmd)switch(cmd)case 'c':case 'C': Initialize();LCSLengt

13、h(m,n,x,y,c,b); Display();Realese();break;void LCSLength(int m,int n,string x,string y,int *c,int*b)int i,j;for(i=0;i<=m;i+)ci0=0;for(i=1;i<=n;i+)c0i=0;for(i=1;i<=m;i+)for(j=1;j<=n;j+)if(xi-1=yj-1)cij=ci-1j-1+1;bij=1;else if(ci-1j>=cij-1)cij=ci-1j;bij=2;elsecij=cij-1;bij=3; /構(gòu)造最長公共子序列

14、void LCS(int i,int j,string x,int *b)if(i=0|j=0)return;if(bij=1)LCS(i-1,j-1,x,b);cout<<xi-1;else if(bij=2)LCS(i-1,j,x,b);else LCS(i,j-1,x,b);void Display()LCS(m,n,x,b);cout<<"n請按回車鍵繼續(xù)！n"cin.get();cin.get();5 課程設(shè)計總結(jié)5.1 程序運(yùn)行結(jié)果或預(yù)期運(yùn)行結(jié)果5.2 設(shè)計結(jié)論回顧起此課程設(shè)計，至今我仍感慨頗多，從理論到實(shí)踐，在這段日子里，可以說得是苦多

15、于甜，但是可以學(xué)到很多很多的東西，同時不僅可以鞏固了以前所學(xué)過的知識，而且學(xué)到了很多在書本上所沒有學(xué)到過的知識。通過這次課程設(shè)計使我懂得了理論與實(shí)際相結(jié)合是很重要的，只有理論知識是遠(yuǎn)遠(yuǎn)不夠的，只有把所學(xué)的理論知識與實(shí)踐相結(jié)合起來，才能提高自己的實(shí)際動手能力和獨(dú)立思考的能力。實(shí)驗(yàn)過程中，使我更加扎實(shí)的掌握了有關(guān)數(shù)據(jù)結(jié)構(gòu)方面的知識，在設(shè)計過程中雖然遇到了一些問題，但經(jīng)過一次又一次的思考，一遍又一遍的檢查終于找出了原因所在，也暴露出了前期我在這方面的知識欠缺和經(jīng)驗(yàn)不足。實(shí)踐出真知，通過親自動手制作，使我們掌握的知識不再是紙上談兵。過而能改，善莫大焉。在課程設(shè)計過程中，我不斷發(fā)現(xiàn)錯誤，不斷改正，不斷領(lǐng)

16、悟，不斷獲取。最終的調(diào)試運(yùn)行環(huán)節(jié)，本身就是在踐行“過而能改，善莫大焉”的知行觀。這次課程設(shè)計終于順利完成了，在設(shè)計中遇到了很多問題，最后在老師的指導(dǎo)下，終于迎刃而解。在今后社會的發(fā)展和學(xué)習(xí)實(shí)踐過程中，一定要不懈努力，不能遇到問題就想到要退縮，一定要不厭其煩的發(fā)現(xiàn)問題所在，然后一一進(jìn)行解決，只有這樣，才能成功的做成想做的事，才能在今后的道路上劈荊斬棘，而不是知難而退，那樣永遠(yuǎn)不可能收獲成功，收獲喜悅，也永遠(yuǎn)不可能得到社會及他人對你的認(rèn)可！此次設(shè)計也讓我明白了思路即出路，有什么不懂不明白的地方要及時請教或上網(wǎng)查詢，只要認(rèn)真鉆研，動腦思考，動手實(shí)踐，就沒有弄不懂的知識，收獲頗豐。參考文獻(xiàn)1張福祥.

17、C語言程序設(shè)計M. 遼寧大學(xué)出版社，2008.12 張福祥，王萌C語言程序設(shè)計習(xí)題解答與實(shí)驗(yàn)實(shí)訓(xùn)M沈陽：遼寧大學(xué)出版社，20083 牛莉，劉遠(yuǎn)軍等計算機(jī)等級考試輔導(dǎo)教程M北京：中國鐵道出版社，2008致 謝本課題在選題及進(jìn)行過程中得到李仲生老師的悉心指導(dǎo)。論文行文過程中，李老師多次幫助我分析思路，開拓視角，在我遇到困難想放棄的時候給予我最大的支持和鼓勵。李老師嚴(yán)謹(jǐn)求實(shí)的治學(xué)態(tài)度，踏實(shí)堅韌的工作精神，將使我終生受益。再多華麗的言語也顯蒼白。在此，謹(jǐn)向李老師致以誠摯的謝意和崇高的敬意。課程設(shè)計(論文)題 目 名 稱 最長公共子序列（動態(tài)規(guī)劃法） 課 程 名 稱 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 學(xué) 生 姓 名 張

18、強(qiáng) 學(xué) 號 系 、專 業(yè) 信息工程系、通信工程 指 導(dǎo) 教 師 李仲生 2011年 12 月 25 日邵陽學(xué)院課程設(shè)計（論文）評閱表學(xué)生姓名 張強(qiáng) 學(xué) 號 系 信息工程系 專業(yè)班級 通信工程一班 題目名稱 最長公共子序列（動態(tài)規(guī)劃法） 課程名稱 數(shù)據(jù)結(jié)構(gòu) 一、學(xué)生自我總結(jié)通過這次課程設(shè)計，綜合運(yùn)用本專業(yè)所學(xué)課程的理論和實(shí)際知識進(jìn)行一次最長公共子序列設(shè)計訓(xùn)練從而培養(yǎng)和提高我獨(dú)立工作能力，鞏固與擴(kuò)充了數(shù)據(jù)結(jié)構(gòu)等課程所學(xué)的內(nèi)容，基本掌握用動態(tài)規(guī)劃法求公共子序列設(shè)計的方法，同時各科相關(guān)的課程都有了全面的復(fù)習(xí)，獨(dú)立思考的能力也有了提高。在設(shè)計過程中雖然遇到了一些問題，但經(jīng)過一次又一次的思考，一遍又一遍的

19、檢查終于找出了原因所在，也暴露出了前期我在這方面的知識欠缺和經(jīng)驗(yàn)不足。此次設(shè)計也讓我明白了思路即出路，有什么不懂不明白的地方要及時請教或上網(wǎng)查詢，只要認(rèn)真鉆研，動腦思考，動手實(shí)踐，就沒有弄不懂的知識，收獲頗豐。 學(xué)生簽名： 張強(qiáng) 2011 年 12月 7日二、指導(dǎo)教師評定評分項(xiàng)目資料查閱編寫規(guī)范基本技能設(shè)計能力科學(xué)素養(yǎng)工作量綜合成績權(quán) 重101525301010單項(xiàng)成績指導(dǎo)教師評語： 指導(dǎo)教師（簽名）： 年 月 日注：1、本表是學(xué)生課程設(shè)計（論文）成績評定的依據(jù)，裝訂在設(shè)計說明書（或論文）的“任務(wù)書”頁后面；2、表中的“評分項(xiàng)目”及“權(quán)重”根據(jù)各系的考核細(xì)則和評分標(biāo)準(zhǔn)確定。邵陽學(xué)院課程設(shè)計（論文）任務(wù)書年級專業(yè)10級通信工程學(xué)生姓名張強(qiáng)學(xué) 號題目名稱最長公共子序列（動態(tài)規(guī)劃法）設(shè)計時間1718周課程名稱數(shù)據(jù)結(jié)構(gòu)課程設(shè)計課程