最長公共子序列代碼和實驗報告.doc

院 系：計 算 機 學(xué) 院實驗課程：算法分析與設(shè)計實驗實驗項目：實驗一（動態(tài)規(guī)劃法算法）指導(dǎo)老師： 曹霑懋 開課時間：2010 2011年度第 2學(xué)期專 業(yè)：計算機科學(xué)與技術(shù) 師范類班 級：09級 2 班學(xué) 生： 程毅學(xué) 號： 20092101056華南師范大學(xué)教務(wù)處實驗名稱：動態(tài)規(guī)劃算法（綜合性實驗）實驗?zāi)繕耍菏褂脛討B(tài)規(guī)劃法和回溯法生成兩個長字符串的最優(yōu)化比對結(jié)果。實驗任務(wù)：把兩個字符串放在一個二維矩陣中，把相同的字符盡最大可能放入同一列（使得整個的比對總計分最大）。字符串S1，S2 分別放在二維矩陣的第一行和第2行，不可錯行。字符可以在行內(nèi)移動，通過插入空格使得共同的片段置于共同的列。實驗步驟：1.明確實驗?zāi)繕撕蛯嶒炄蝿?wù) 2.理解實驗所涉及到的最長公共子序列的算法 3.編寫程序?qū)崿F(xiàn)求兩個字符串的最長公共子序列的長度。 4.設(shè)計實驗數(shù)據(jù)數(shù)據(jù)并運行程序，記錄運行的結(jié)果程序代碼: #include#include#includeusing namespace std;int dp10001000;string str1,str2,s1,s2;int max(int a,int b,int c)if(ab & ac)return a;if(ba & bc)return b;if(ca & cb)return c;int lcs(int len1,int len2)memset(dp,0,sizeof(dp);int i,j,x; dp01=0;dp10=0;dp11=0;dp00=0; for(i=2;ilen1+2;i+)dpi1=-2*(i-1);for(j=2;jlen2+2;j+)dp1j=-2*(j-1);for(j=2;jlen2+2;j+)for(i=2;i1 & j1)if(dpij+2=dpi-1j)s2=s2+_;s1=s1+str1i-2;i-;continue;if(dpij+2=dpij-1)s1=s1+_;s2=s2+str2j-2;j-;continue;if(dpij+1=dpi-1j-1 | dpij-5=dpi-1j-1)s1=s1+str1i-2;s2=s2+str2j-2;j-;i-;continue;for(i=len1-1;i=0;i-)couts1i;cout=0;j-)couts2j;coutstr1str2)len1=str1.size();len2=str2.size(); coutlcs(len1,len2)endl;for(int i=1;i=len1+1;i+)for(int j=1;j=len2+1;j+)coutsetw(5)dpij ;coutendl; print(len1,len2);return 0;數(shù)據(jù)測試： 實驗小結(jié)： 通過這次實驗，對動態(tài)規(guī)劃法求最長公共子序列有更深的理解。其實無非就是抓住書上的遞推公式進行寫而已。動態(tài)規(guī)劃依賴于上一個或者上一行的解。就是在輸出子序列的時候有問題。就是一開始，不知道那個橫線放在哪里。后來修改過后終于行了?？偟脕碚f，實驗還是很順利的。遺憾的是，沒有完全吃透