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

1、word最長(zhǎng)公共子序列問(wèn)題 一 實(shí)驗(yàn)?zāi)康模?1. 加深對(duì)最長(zhǎng)公共子序列問(wèn)題算法的理解，實(shí)現(xiàn)最長(zhǎng)公共子序列問(wèn)題的求解算法；2. 通過(guò)本次試驗(yàn)掌握將算法轉(zhuǎn)換為上機(jī)操作；3. 加深對(duì)動(dòng)態(tài)規(guī)劃思想的理解，并利用其解決生活中的問(wèn)題。二 實(shí)驗(yàn)內(nèi)容：1. 編寫(xiě)算法：實(shí)現(xiàn)兩個(gè)字符串的最長(zhǎng)公共子序列的求解；2. 將輸入與輸出數(shù)據(jù)保存在文件之中，包括運(yùn)行時(shí)間和運(yùn)行結(jié)果；3. 對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析。三 實(shí)驗(yàn)操作：1. 最長(zhǎng)公共子序列求解： 將兩個(gè)字符串放到兩個(gè)字符型數(shù)組中，characterString1和characterString2，當(dāng)characterString1m= characterString2m時(shí)，

2、找出這兩個(gè)字符串m之前的最長(zhǎng)公共子序列，然后在其尾部加上characterString1m，即可得到最長(zhǎng)公共子序列。當(dāng)characterString1m characterString2m時(shí)，需要解決兩個(gè)子問(wèn)題：即找出characterString1(m-1)和characterString2的一個(gè)最長(zhǎng)公共子序列及characterString1和characterString2(m-1)的一個(gè)最長(zhǎng)公共子序列，這兩個(gè)公共子序列中較長(zhǎng)者即為characterString1和characterString2的一個(gè)最長(zhǎng)公共子序列。2. 動(dòng)態(tài)規(guī)劃算法的思想求解：動(dòng)態(tài)規(guī)劃算法是自底向上的計(jì)算最優(yōu)值。計(jì)算

3、最長(zhǎng)公共子序列長(zhǎng)度的動(dòng)態(tài)規(guī)劃算法LCS-Length以characterString1和characterString2作為輸入，輸出兩個(gè)數(shù)組result和judge1，其中result存儲(chǔ)最長(zhǎng)公共子序列的長(zhǎng)度，judge1記錄指示result的值是由那個(gè)子問(wèn)題解答得到的，最后將最終的最長(zhǎng)公共子序列的長(zhǎng)度記錄到result中。以L(fǎng)CS-Length計(jì)算得到的數(shù)組judge1可用于快速構(gòu)造序列最長(zhǎng)公共子序列。首先從judge1的最后開(kāi)始，對(duì)judge1進(jìn)行配對(duì)。當(dāng)遇到“時(shí)，表示最長(zhǎng)公共子序列是由characterString1(i-1)和characterString2(j-1)的最長(zhǎng)公共子序列

4、在尾部加上characterString1(i)得到的子序列；當(dāng)遇到“時(shí)，表示最長(zhǎng)公共子序列和characterString1(i-1)與characterString2(j)的最長(zhǎng)公共子序列相同；當(dāng)遇到“時(shí)，表示最長(zhǎng)公共子序列和characterString1(i)與characterString2(j-1)的最長(zhǎng)公共子序列相同。如下圖：時(shí)間復(fù)雜度公式：代碼實(shí)現(xiàn)：void LCSLength(char* characterString1,char* characterString2,int length1,int length2,int judge10000) int result10010

5、0; for(int i=0;i<=length1;i+) resulti0=0; for(int j=1;j<=length2;j+) result0j = 0; for(int i=1;i<=length1;i+) for(int j=1;j<=length2;j+) if(characterString1i-1=characterString2j-1) resultij=resulti-1j-1+1; judgeij=0; else if(resulti-1j>=resultij-1) resultij=resulti-1j; judgeij=1; else

6、 resultij=resultij-1; judgeij=-1; void LCS(int judge10000,char* characterString1,int length1,int length2)/得到最長(zhǎng)公共子序列 if(length1=0|length2=0) return; if(judgelength1length2=0) LCS(judge,characterString1,length1-1,length2-1); record(characterString1length1-1);/存入文件 cout<<characterString1length1-1

7、; else if(judgelength1length2=1) LCS(judge,characterString1,length1-1,length2); else LCS(judge,characterString1,length1,length2-1); 3. 備忘錄算法實(shí)現(xiàn)： 備忘錄算法是從頂向下計(jì)算最優(yōu)解的思想，備忘錄方法的控制結(jié)構(gòu)與直接遞歸方法的控制結(jié)構(gòu)相同，但備忘錄方法用一個(gè)表格來(lái)保存已解決的子問(wèn)題的答案，防止了相同問(wèn)題的重復(fù)求解。 代碼實(shí)現(xiàn)： int searchLCS(char* characterString1,char* characterString2,int len

8、gth1,int length2) if(judge2length1length2>-1) return judge2length1length2; if(length1=0|length2=0) judge2length1length2=0; else if(characterString1length1-1=characterString2length2-1) judge2length1length2=searchLCS(characterString1,characterString2,length1-1,length2-1)+1; else judge2length1length

9、2=max(searchLCS(characterString1,characterString2,length1,length2-1), searchLCS(characterString1,characterString2,length1-1,length2); return judge2length1length2;int memorizedLCS(char* characterString1,char* characterString2) int length1=strlen(characterString1); int length2=strlen(characterString2)

10、; for(int i=1;i<=length1;i+) for(int j=1;j<=length2;j+) judge2ij=-1; return searchLCS(characterString1,characterString1,length1,length2); 4. 遞歸法：設(shè)有字符串characterString1和characterString2，當(dāng)兩個(gè)數(shù)組的對(duì)應(yīng)位置的字符相同時(shí)，那么直接求解下一個(gè)位置，當(dāng)不同時(shí)取兩種情況中的最大值。時(shí)間復(fù)雜度公式：代碼實(shí)現(xiàn)：int recursionLCS(int i,int j,int length1) if(i>=le

11、ngth1|j>=length2) return 0; if(characterString1i=characterString2j) return 1+recursionLCS(i+1,j+1); else return recursionLCS(i+1,j)>recursionLCS(i,j+1)recursionLCS(i+1,j):recursionLCS(i,j+1);5. 窮舉法： 將數(shù)組characterString1和characterString2兩個(gè)字符串的所有字串求出，并將這些字串相互比擬，直到找的最長(zhǎng)公共子序列為止，當(dāng)字符串的長(zhǎng)度很長(zhǎng)時(shí)，所要求取的子串序列相當(dāng)多，故所開(kāi)銷(xiāo)的時(shí)間最多。四 實(shí)驗(yàn)結(jié)果分析： 當(dāng)輸入字符串長(zhǎng)度分別為20,20，34,78，98,145時(shí)，在動(dòng)態(tài)規(guī)劃算法、備忘錄算法、遞歸算法得到的時(shí)間分別為0,0,0，0,16,22，0,16,34