求最大公共序列.doc

《求最大公共序列.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、求最大公共子序列一．实验目的1．掌握动态规划法的设计思想并能熟练运用2．强化动手编程的能力二．实验内容用动态规划法求两个序列的最大公共子序列三．算法思想1．分析可得如下动态规划函数：①L[0][0]=L[i][0]=L[0][j]=0（1<=i<=m,1<=j<=n）②L[i][j]=L[i-1][j-1]+1(Xi=Yi,I>1,j>1);或者max{L[i][j-1],L[i-1][j]}(Xi!=Yi,i>1,j>1)2.由此函数，把序列X={x1,x2….xm}和Y={y1,y2…ym}的最长公共子序列的搜索分为M个阶段，第1阶段，按照式1计算X1和Yj的最长公共子序列长度L[1][j

2、](1<=j<=n),第2阶段，按照2式计算X2和Yj的最长公共子序列长度L[2][j]（1<=j<=n）,以此类推，最后在第M阶段，计算Xm和Yj的最长公共子序列长度L[m][j]（1<=j<=n）,则L[m][n]就是序列Xm和Yn的最长公共子序列的长度。运行结果：附：源代码：#includeusingnamespacestd;voidlsc(chara[],intla,charb[],intlb);voidmain(){chara[20];charb[20];inti=0;intnum=0;charc;a[0]='';i=1;cout<<"请输入字符串a:"<

3、l;do{c=cin.get();if(c=='')break;if(c!='')a[i++]=c;}while(i<20);intlen1=i;i=1;cout<<"请输入字符串b:"<

4、;}for(i=0;i=0&&j>=0)

5、{if(m[i][j]==max){if(a[i]==b[j]){output[no]=a[i];no++;i--;j--;max--;}else{if(m[i-1][j]=0;i--)cout<