算法 最長公共子序列_第1頁
算法 最長公共子序列_第2頁
算法 最長公共子序列_第3頁
算法 最長公共子序列_第4頁
全文預覽已結(jié)束

下載本文檔

版權說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權，請進行舉報或認領

文檔簡介

本文格式為Word版，下載可任意編輯——算法最長公共子序列

算法最長公共子序列

最長公共子序列

1題目分析

兩個序列的最長公共子序列的長度為最優(yōu)值，利用動態(tài)規(guī)劃法

2算法構造

引入二維數(shù)組C[i,j]記錄Xi=xl,x2,…,xi和Yj=二y1;y2,,…,yj根據(jù)子問題最優(yōu)值的遞歸關系，可自底向上建立遞推關系如下：

當i=0,j=0時,c[i][j]=0

當i,j0;xi=yi時,c[i][j]=c[i-1][j-1]+1

當i,j0;xi!=yi時,c[i][j]=max{c[i][j-1],c[i-1][j]}

3算法實現(xiàn)

#includeiostream

#includestring

usingnamespacestd;

//計算最優(yōu)值

voidLCSLength(intm,intn,char*y,char*x,int**c,int**b)

{

inti,j;

for(i=1;i=m;i++)c[i][0]=0;

for(j=0;j=n;j++)c[0][j]=0;

for(i=1;i=m;i++)

for(j=1;j=n;j++)

{

if(x[i]==y[j]){c[i][j]=c[i-1][j-1]+1;b[i][j]=1;}

elseif(c[i-1][j]=c[i][j-1]){c[i][j]=c[i-1][j];b[i][j]=2;}

else{c[i][j]=c[i][j-1];b[i][j]=3;}

}

}

//構造最長公共子序列

voidLCS(inti,intj,char*x,int**b)

{

if(i==0||j==0)return;

if(b[i][j]==1){LCS(i-1,j-1,x,b);coutx[i];}

elseif(b[i][j]==2)LCS(i-1,j,x,b);

elseLCS(i,j-1,x,b);

}

//主函數(shù)

intmain()

{

算法最長公共子序列

intm,n;

char*x,*y;

int**b,**c;

voidLCSLength(intm,intn,char*y,char*x,int**c,int**b);voidLCS(inti,intj,char*x,int**b);

cout請輸入兩個序列的長度：endl;

cinmn;

x=newchar[m];

y=newchar[n];

cout請輸入兩個序列：endl;

cinxy;

b=newint*[m+1];

for(inti=0;i=m;i++)

b[i]=newint[n+1];

c=newint*[m+1];

for(intj=0;j=m;j++)

c[j]=newint[n+1];

LCSLength(m,n,x,y,c,b);

cout最長公共子序列的元素個數(shù)為c[m][n]endl;

cout該序列為:;

LCS(m,n,x,b);

coutendl;

return0;

}

4運行結(jié)果

請輸入兩個序列的長度：

5

5

請輸入兩個序列：

dfdhh

溫馨提示

  • 1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
  • 4. 未經(jīng)權益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負責。
  • 6. 下載文件中如有侵權或不適當內(nèi)容，請與我們聯(lián)系，我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論