最長(zhǎng)公共子序列代碼和實(shí)驗(yàn)報(bào)告.doc

院 系：計(jì) 算 機(jī) 學(xué) 院實(shí)驗(yàn)課程：算法分析與設(shè)計(jì)實(shí)驗(yàn)實(shí)驗(yàn)項(xiàng)目：實(shí)驗(yàn)一（動(dòng)態(tài)規(guī)劃法算法）指導(dǎo)老師： 曹霑懋 開課時(shí)間：2010 2011年度第 2學(xué)期專 業(yè)：計(jì)算機(jī)科學(xué)與技術(shù) 師范類班 級(jí)：09級(jí) 2 班學(xué) 生： 程毅學(xué) 號(hào)： 20092101056華南師范大學(xué)教務(wù)處實(shí)驗(yàn)名稱：動(dòng)態(tài)規(guī)劃算法（綜合性實(shí)驗(yàn)）實(shí)驗(yàn)?zāi)繕?biāo)：使用動(dòng)態(tài)規(guī)劃法和回溯法生成兩個(gè)長(zhǎng)字符串的最優(yōu)化比對(duì)結(jié)果。實(shí)驗(yàn)任務(wù)：把兩個(gè)字符串放在一個(gè)二維矩陣中，把相同的字符盡最大可能放入同一列（使得整個(gè)的比對(duì)總計(jì)分最大）。字符串S1，S2 分別放在二維矩陣的第一行和第2行，不可錯(cuò)行。字符可以在行內(nèi)移動(dòng)，通過插入空格使得共同的片段置于共同的列。實(shí)驗(yàn)步驟：1.明確實(shí)驗(yàn)?zāi)繕?biāo)和實(shí)驗(yàn)任務(wù) 2.理解實(shí)驗(yàn)所涉及到的最長(zhǎng)公共子序列的算法 3.編寫程序?qū)崿F(xiàn)求兩個(gè)字符串的最長(zhǎng)公共子序列的長(zhǎng)度。 4.設(shè)計(jì)實(shí)驗(yàn)數(shù)據(jù)數(shù)據(jù)并運(yùn)行程序，記錄運(yùn)行的結(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ù)測(cè)試： 實(shí)驗(yàn)小結(jié)： 通過這次實(shí)驗(yàn)，對(duì)動(dòng)態(tài)規(guī)劃法求最長(zhǎng)公共子序列有更深的理解。其實(shí)無非就是抓住書上的遞推公式進(jìn)行寫而已。動(dòng)態(tài)規(guī)劃依賴于上一個(gè)或者上一行的解。就是在輸出子序列的時(shí)候有問題。就是一開始，不知道那個(gè)橫線放在哪里。后來修改過后終于行了。總得來說，實(shí)驗(yàn)還是很順利的。遺憾的是，沒有完全吃透