2017年计算机等级考试二级C++辅导：最长公共子序列

2017年计算机等级考试二级C++辅导：最长公共子序列一、算法思想一个给定序列的子序列是在该序列中删去若干元素后得到的序列。给定两个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。最长公共子序列就是求给定两个序列的一个最长公共子序列。动态规划可以有效的解决此问题。由最长公共子序列问题的子序列的子结构性质，可以建立子问题的递归关系。用c[i][j]记录序列Xi和Yi的最长公共子序列的长度，递归关系如下：0i=0,j=0c[i][j]=c[i-1][j][j-1]+1i,j>0;xi==yjmaxc[i][j-1],c[i-1][j]I,j>0;xi==yj在具体的算法设计中，以序列X={x1,x2,x3,…,xm}和Y={y1,y2,y3,…,ym}作为输入。输出三个数组c,b,temp。其中c[i][j]存储Xi和Yj的公共子序列的长度，b[i][j]记录c[i][j]的值是由哪一个子问题的解得到的，这在构造最长公共子序列时要用到。问题得解，即X和Y得最长公共子序列记录在temp[h]中。二、源代码下面是在MicrosoftVisualC++6.0中编写的求最长公共子序列的源程序，程序定义了得字符串长度为99，是将p48页的动态规划算法改写而来的。#include#include#defineMAX99//typedefcharMM;voidmain(){inti,j,m,n,h=0;charx[MAX]={'',''},y[MAX]={'',''},b[MAX][MAX]={''};intc[MAX][MAX]={0};chartemp[MAX]={''};cout<<"**本程序可以求得字符数在99以内的任意两个字符串的公共子序列**\n";cout<<"请输入第一个字符串的长度m=";cin>>m;cout<<"请输入第一个字符串(“回车”结束)\n如果输入的字符数超过m,则会出错!\nx["<for(i=1;i<=m;i++)cin>>x[i];//键盘输入x和ycout<<"请输入第二个字符串的长度n=";cin>>n;cout<<"请输入第二个字符串\ny["<for(i=1;i<=n;i++)cin>>y[i];for(i=1;i<=m;i++)c[i][0]=0;//动态规划开始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]='\\';}elseif(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]='-';}}//动态规划结束cout<<"c[m][n]中的内容：\n";for(i=0;i<=m;i++){for(j=0;j<=n;j++)cout<cout<}cout<<"b[m][n]中的内容：\n";for(i=1;i<=m;i++){for(j=1;j<=n;j++)cout<cout<}i=m,j=n;while(1){if(i==0││j==0)break;if(b[i][j]=='\\'){temp[h++]=x[i];//反序记录最长公共子序列到temp中i=i-1,j=j-1;}elseif(b[i][j]=='│')i=i-1;elsej=j-1;}cout<<"\nx["<for(i=h-1;i>=0;i--)//格式化输出最长公共子序列if(i==h-1)if(h==1)cout<<"LCS:<"<elsecout<<"LCS:<"<elseif(i==0)cout<<","<elsecout<<","<cout<<"\n"<}三、运算结果其实它的最长公共子序列不止一个，这里只输出了其中的一个。四、总结分析在这个具体的算法中，还有可以改进的地方，比如在具体的求公共子序列中，可以不必要MAX的宏定义，只需将各数组设为具体的长度就可以节约不少的空间，大大降低程序的空间复杂度，但是为了键盘输入任意字符串，牺牲了很多的内存空间。在键盘输入字符