82实验四

华侨大学算法设计与分析实验报告实验四姓名：黄有财专业：软件工程班级：软3学号：1325113007一．导言1)问题的描述应用动态规划法求出两个序列中最长的公共子序列及其长度。分析时间和空间复杂度。例如，”123”和”132”的最长公共子序列是”12”。2)拟采用的方法以两个序列的最长公共子序列的长度为最优值，利用动态规划法，引入二维数组C[i,j]记录Xi=xl,x2,…,xi和Yj=y1y2,,…,yj的最长公共子序列的长度。根据子问题最优值的递归关系，可自底向上建立递推关系如下：二．实验过程#includeiostreamusingnamespacestd;voidmain(){chara[100],b[100],s[100];intc[100][100],n1,n2,i,j,length;cout输入第一个序列的长度n1=;cinn1;cout输入第一个序列值;for(i=0;in1;i++)cina[i];cout输入第二个序列的长度n2=;cinn2;cout输入第二个序列值;for(i=0;in2;i++)cinb[i];coutendl;for(i=0;i=n1;i++)c[i][0]=0;//将第一列设置为零；for(j=0;j=n2;j++)c[0][j]=0;//将第一行设置为零；for(i=1;i=n1;i++)for(j=1;j=n2;j++){if(a[i-1]==b[j-1])//当两个数相等的时候；c[i][j]=c[i-1][j-1]+1;else//不相等将大一点的数赋值给船[i][j]；{if(c[i][j-1]c[i-1][j])c[i][j]=c[i][j-1];elsec[i][j]=c[i-1][j];}length=c[n1][n2];}cout最大公共子序列长度为lengthendl;cout;for(i=0;in2;i++)coutb[i];coutendl;for(i=0;i=n1;i++){if(i!=n1)couta[i];elsecout;for(j=0;j=n2;j++){coutc[i][j];}coutendl;}//输出二位数组c[i][j];intk=length;while(k0){if(c[n1][n2]==c[n1-1][n2])n1--;elseif(c[n1][n2]==c[n1][n2-1])n2--;else{s[k-1]=a[n1-1];k--;n1--;n2--;}}//对c[i][j]数组进行比对；找不到相同的数则将此刻的值赋值给s[k-1];否则继续循环；cout两个序列的公共子序列是：;for(i=0;ilength;i++)couts[i];coutendl;}三．结果分析1)实验环境c++2)实验结果时间复杂度O（n）=n1*n2；