




全文預覽已結束
下載本文檔
版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領
文檔簡介
第五次實驗報告最長公共子序列的生成算法1.1算法應用背景最長公共子序列是一個序列S ,如果分別是兩個或多個已知序列的子序列,且是所有符合此條件序列中最長的,則S稱為已知序列的最長公共子序列。而最長公共子串(要求連續(xù))和最長公共子序列是不同的。最長公共子序列是一個十分實用的問題,它可以描述兩段文字之間的“相似度”,即它們的雷同程度,從而能夠用來辨別抄襲。對一段文字進行修改之后,計算改動前后文字的最長公共子序列,將除此子序列外的部分提取出來,這種方法判斷修改的部分,往往十分準確。簡而言之,百度知道、百度百科都用得上。1.2算法原理 若給定序列X=x1,x2,xm,則另一序列Z=z1,z2,zk,是X的子序列是指存在一個嚴格遞增下標序列i1,i2,ik使得對于所有j=1,2,k有:zj=xij。例如,序列Z=B,C,D,B是序列X=A,B,C,B,D,A,B的子序列,相應的遞增下標序列為2,3,5,7。例: = x, y, z ,A = x y z y x z x z x x x 是長度為 3 的子序列 x z y z x 是長度為 5 的子序列例:A = x y z y x z x z,B = x z y x x y z x x x x是長度為 3 的公共子序列 x z y z 是長度為 4 的公共子序列 x z y x x z是長度為 6 的最長公共子序列1.3算法描述記Ln,m為序列An和Bm的最長公共子序列長度,則Li,j為序列Ai和Bj的最長公共子序列的長度。根據(jù)最長公共子序列的性質,則得到:階段的劃分和最長公共子序列長度的獲取第一階段:計算A1和Bj的最長公共子序列的長度 L1,j ,j=1,2,m第二階段:計算A2和Bj的最長公共子序列的長度 L2,j, j=1,2,m第 n 階段:計算An和Bj的最長公共子序列的長度 Ln,j, j=1,2,m第 n 階段的Lm,n便是序列An和Bm的最長公共子序列的長度為了得到An和Bm最長公共子序列,設置一個二維的狀態(tài)字數(shù)組si,j,在上述每一個階段計算Ln,j 過程中,根據(jù)公共子序列的性質則有按照如下方法把搜索狀態(tài)登記于狀態(tài)字si,j中: si,j =1 ai=bjsi,j =2 aibj Li-1,j= Li,j-1si,j =3 aibj Li-1,j= Li,j-1下一個搜索方向是Sn-1,mSm,n =3 aibj Li-1,j Li,j-1 下一個搜索方向是Sn,m-1遞推關系: 若si,j =1 則ck=ai,i=i-1,j=j-1,k=k-1si,j =2 aibj 則i=i-1si,j =3 aibj 則j=j-1從i=n,j=m開始搜索,直到i=0或j=0結束,即可得到An和Bm的最長公共子序列。1.4程序實現(xiàn)及程序截圖1.4.1程序源碼5#include #include #define MAXLEN 100void LCSLength(char *x, char *y, char *z,int m, int n, int cMAXLEN, int bMAXLEN) int i,j,k,len; for(i = 0; i = m; i+) ci0 = 0; for(j = 1; j = n; j+) c0j = 0; for(i = 1; i= m; i+) for(j = 1; j = cij-1) cij = ci-1j; bij = 2; else cij = cij-1; bij = 3; i=m;j=n;k=len=cij;while (i!= 0) &(j != 0) / printf(%d %dn,i,j);switch (bij) case 1: zk=xi-1;k-;j-; case 2:i-;break; case 3:j-;break;printf(最長公共子序列長度n); for (i=1;i=m;i+)for (j=1;j=n;j+)printf(%d ,cij);printf(n); printf(最長公共子序列字符比較n);for (i=1;i=m;i+)for (j=1;j=n;j+)printf(%d ,bij);printf(n);printf(最長公共子序列為:);for (i=1;i=len;i+)printf(%c,zi);printf(n);int main(int argc, char *argv) char xMAXLEN; char yMAXLEN;char zMAXLEN; int bMAXLENMAXLEN; int cMAXLENMAXLEN; int m, n; printf(請按照提示輸入兩個字符串n);printf(請輸入第一個字符串:);scanf(%s,x); printf(請輸入第二個字符串:);scanf(%s,y)
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經(jīng)權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
- 6. 下載文件中如有侵權或不適當內容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 預防幼兒流感知識課件
- 預防醫(yī)學健康課件
- 采收梨瓜技術培訓課件
- 順境逆境說課課件
- 項鏈小說介紹課件
- 《金屬工藝學》課件-第三章 鋼鐵材料
- 職場心理健康培訓體系構建
- 音樂游戲培訓課件
- 2025年耐輻照電絕緣玻璃纖維合作協(xié)議書
- 鄉(xiāng)鎮(zhèn)基層農業(yè)經(jīng)濟統(tǒng)計分析
- 網(wǎng)絡安全產業(yè)學院建設規(guī)劃方案
- 2024年秋季新人教版八年級上冊物理全冊教案(2024年新教材)
- 內河航道例行養(yǎng)護工程預算編制規(guī)定及定額編制說明
- 2024年全國民政行業(yè)職業(yè)技能大賽(養(yǎng)老護理員賽項)備賽試題庫及答案
- 英文繪本故事Brown.Bear.Brown.Bear.What.Do.You.See
- 2024-2029年中國駕駛艙監(jiān)視系統(tǒng)行業(yè)市場現(xiàn)狀供需分析及市場深度研究發(fā)展前景及規(guī)劃戰(zhàn)略投資分析研究報告
- 2024年社區(qū)工作者考試必背1000題題庫必背(典型題)
- (正式版)JBT 7248-2024 閥門用低溫鋼鑄件技術規(guī)范
- 關于垃圾分類的調查研究報告
- 靜電對電子器件的影響與防護措施
- 簡易借條模板
評論
0/150
提交評論