最長公共子序列實驗報告

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

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

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

4、在尾部加上characterString1(i)得到的子序列；當(dāng)遇到“時，表示最長公共子序列和characterString1(i-1)與characterString2(j)的最長公共子序列相同；當(dāng)遇到“時，表示最長公共子序列和characterString1(i)與characterString2(j-1)的最長公共子序列相同。如下圖：時間復(fù)雜度公式：代碼實現(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)/得到最長公共子序列 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. 備忘錄算法實現(xiàn)： 備忘錄算法是從頂向下計算最優(yōu)解的思想，備忘錄方法的控制結(jié)構(gòu)與直接遞歸方法的控制結(jié)構(gòu)相同，但備忘錄方法用一個表格來保存已解決的子問題的答案，防止了相同問題的重復(fù)求解。 代碼實現(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)兩個數(shù)組的對應(yīng)位置的字符相同時，那么直接求解下一個位置，當(dāng)不同時取兩種情況中的最大值。時間復(fù)雜度公式：代碼實現(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兩個字符串的所有字串求出，并將這些字串相互比擬，直到找的最長公共子序列為止，當(dāng)字符串的長度很長時，所要求取的子串序列相當(dāng)多，故所開銷的時間最多。四 實驗結(jié)果分析： 當(dāng)輸入字符串長度分別為20,20，34,78，98,145時，在動態(tài)規(guī)劃算法、備忘錄算法、遞歸算法得到的時間分別為0,0,0，0,16,22，0,16,34