资源描述：
《实验四：动态规划法求最长子序列》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、实验四：动态规划法求两个序列的最长公共子序列及其长度姓名：刘桂莲班级：计科2班（数字媒体）学号：1025113018实验内容应用第8章的动态规划法求出两个序列屮最长的公共子序列及其长度。分析时间复杂度。例如，”123”和”132”的扱长公共子序列是”12”（不一定是连续的）。算法思想•动态规划的思想：-对较小的子问题进行一次求解，并把结果记录下来，然后利用较小问题的解,求解出较大问题的解，直到求解出最大问题的解。0if/=0orj=(K(■[/-l.y-l
2、+1if/j'>0and.v(=，max((仏j-1-kjl)if/j'>0andA；.引进一个二维数组ch[MAX][MAX]，用ch[
3、i][j]记录CHI与CH2的LCS的长度，b[i][j]记录ch[i][j]是通过哪一个子问题的值求得的，以决定搜索的方向。我们是自底向上进行递推计算，那么在计算ch[i，j]之前，ch[i-l][j-l],ch[i-l][j]与ch[i][j-l]均己计算出来。此吋我们根据CHI[i]=CH2[j]还是CHl[i]!=CH2[j],就可以计算出ch[i][j]。算法length(stringCHI,stringCH2,intb[MAX][MAX])//用于构建动态数组//输入：两字符窜//输出：最长公共子序列for(i=1;i<=ch1Len;i++)//二重循环求解for(intj=l;
4、j<=ch2Len;j++)if(CHl[i-l]==CH2fj-l])//相等字符{ch[i]U]=ch[i-l]U-l]+l;b[i]U]=O;}elseif(ch[i-1][j]>=ch[i][j-l])//上比较大{ch[i][j]=ch[i-l]U];b卿=1;}else//左比较大{ch[i][j]=ch[i]
5、j-l];bUJUJ=-l；}}printCS(intb[MAX][MAX],stringx,inti,intj)//回溯求出®长子序列输出//输入：标记数组//输出：最长子序列1叩=()
6、
7、』二=0)//边界，返回return;if(b[i]u]==o){printCS(
8、b,x,i-1，j-1);//左上cout«x[i-ll«MH;}elseif(b[i][j]==1)printCS(b，x，i-1，j);//上elseprintCS(b，x，i，j-l);//左源程序#include#include#includeusingnamespacestd;#defineMAX100//糸氺糸氺糸氺糸氺糸氺氺氺氺氺+了~^*******************************^******voidprint(inta[MAX][MAX]，intb,intc)for(inti=0;i<=b;i++)for
9、(intj=O;j<=c;j++)cout«a[i]
10、jj«nH;}cout«endl;}*1^*y*}//氺氺承氺承氺承氺承氺氺氺氺氺氺氺氺氺氺intlength(stringCH1,stringCH2,intb[MAXKMAXl){intch[MAX][MAX],max=l;intchiLen=CH1.length()，ch2Len=CH2.1ength();//求字符窜长度for(inti=O;i<=chlLen;i++)//初始化动态数组为0for(intj=0;j<=ch2Len;j++){ch[i]
11、j]=O;}for(i=1;i<=ch1Len;i++)//二重循环填充动态数组f
12、or(intj=l;j<=ch2Len;j++){if(CHl[i-l]==CH2[j-l])//相等字符{ch[i]o]=ch[i-i]
13、j-i]+i;b[i]U]=O;}elseif(ch[i-l]U]〉=ch[i]Lj-l])//上比较大{//ch[i][j]=Max(ch[i]
14、j-l],ch[i-l][j]);ch[i][j]=ch[i-l][j];bri]fjl=l；}else//左比较大ch[i][j]=ch[i]U-l];b[i]U]=_l;}}cout<<"动态规划矩阵:"«endl;print(ch,ch1Len，ch2Len);//打印动态规划矩阵returnch[ch1
15、Len][ch2Len];voidprintCS(intb[MAXl[MAXl，stringx，inti，intj){if(i==0
16、
17、j==0)return;if(b[iJUJ==0){printCS(b，x，i-1，j-1);//左上cout«x[i-l]«")elseif(b[i][j]==1)printCS(b，x，i-l，j);//上elseprintCS(b，x，i，j-1);//左}
