一、算法思想
一個(gè)給定序列的子序列是在該序列中刪去若干元素后得到的序列。給定兩個(gè)序列X和Y,當(dāng)另一序列Z既是X的子序列又是Y的子序列時(shí),稱Z是序列X 和Y的公共子序列。最長公共子序列就是求給定兩個(gè)序列的一個(gè)最長公共子序列。動(dòng)態(tài)規(guī)劃可以有效的解決此問題。由最長公共子序列問題的子序列的最優(yōu)子結(jié)構(gòu)性質(zhì),可以建立子問題最優(yōu)的遞歸關(guān)系。用c[i][j]記錄序列Xi和Yi的最長公共子序列的長度,遞歸關(guān)系如下:
0 i=0,j=0
c[i][j]= c[i-1][j][j-1]+1 i,j> 0;xi==yj
max c[i][j-1],c[i-1][j] I,j> 0;xi==yj
在具體的算法設(shè)計(jì)中,以序列X= { x1,x2,x3,…,xm }和Y= {y1,y2,y3,…,ym}作為輸入。輸出三個(gè)數(shù)組c,b,temp。其中c[i][j]存儲(chǔ)Xi和Yj的公共子序列的長度,b[i][j]記錄c[i][j]的值是由哪一個(gè)子問題的解得到的,這在構(gòu)造最長公共子序列時(shí)要用到。問題得最優(yōu)解,即X和Y得最長公共子序列記錄在temp[h]中。
二、源代碼
下面是在Microsoft Visual C++ 6.0中編寫的求最長公共子序列的源程序,程序定義了最大得字符串長度為99,是將p48頁的動(dòng)態(tài)規(guī)劃算法改寫而來的。
#include
#include
#define MAX 99
//typedef char MM;
void main()
{ int i,j,m,n,h=0;
char x[MAX]={ ' ', ' '},y[MAX]={ ' ', ' '},b[MAX][MAX]={ ' '};
int c[MAX][MAX]={0};
char temp[MAX]={ ' '};
cout < < "**本程序可以求得字符數(shù)在99以內(nèi)的任意兩個(gè)字符串的最大公共子序列**\n ";
cout < < "請輸入第一個(gè)字符串的長度m= ";
cin> > m;
cout < < "請輸入第一個(gè)字符串(“回車”結(jié)束)\n如果輸入的字符數(shù)超過m,則會(huì)出錯(cuò)!\nx[ " <
for(i=1;i <=m;i++)
cin> > x[i]; //鍵盤輸入x和y
cout < < "請輸入第二個(gè)字符串的長度n= ";
cin> > n;
cout < < "請輸入第二個(gè)字符串\ny[ " <
for(i=1;i <=n;i++)
cin> > y[i];
for(i=1;i <=m;i++)c[i][0]=0; //動(dòng)態(tài)規(guī)劃開始
for(i=1;i <=n;i++)c[0][i]=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]= '\\ ';
}else
if(c[i-1][j]> =c[i][j-1])
{ c[i][j]=c[i-1][j];
b[i][j]= '│ ';
}else{c[i][j]=c[i][j-1];
b[i][j]= '- ';
}
} //動(dòng)態(tài)規(guī)劃結(jié)束
cout < < "c[m][n]中的內(nèi)容:\n ";
for(i=0;i <=m;i++)
{for(j=0;j <=n;j++)
cout <
cout <
}
cout < < "b[m][n]中的內(nèi)容:\n ";
for(i=1;i <=m;i++)
{for(j=1;j <=n;j++)
cout <
cout <
}
北京 | 天津 | 上海 | 江蘇 | 山東 |
安徽 | 浙江 | 江西 | 福建 | 深圳 |
廣東 | 河北 | 湖南 | 廣西 | 河南 |
海南 | 湖北 | 四川 | 重慶 | 云南 |
貴州 | 西藏 | 新疆 | 陜西 | 山西 |
寧夏 | 甘肅 | 青海 | 遼寧 | 吉林 |
黑龍江 | 內(nèi)蒙古 |