Question

（算法 c++）动态规划法求解最长公共子序列 本人菜鸟求高手改错帮忙完成 谢谢了

#include <iostream.h>
#include <string.h>
#define maxlength 11
class LCS
{
public:
LCS(int nx,int ny,char *x,char *y);
void LCSLength();
void CLCS();

private:
void CLCS(int i,int j);
int m,n;
int **c,**s;
char *a,*b;
};
void LCS::LCSLength()
{
for (int i=1;i<=m;i++) c[i][0]=0;
for (int j=1;j<=n;j++) c[0][j]=0;
for (i=1;i<=m;i++)
for (j=1;j<=n;j++)
if (a[i]==b[j])
{
c[i][j]=c[i-1][j-1]+1; s[i][j]=1;
}
else if (c[i-1][j]>=c[i][j-1]) {
c[i][j]=c[i-1][j]; s[i][j]=2;
}
else {
c[i][j]=c[i][j-1]; s[i][j]=3;
}
return c[m][n];
}
LCS(int nx,int ny,char *x,char *y)
{ m=nx; n=ny;
a=new char[m+2];
b=new char[n+2];
memset(a,0,m+2);
memset(b,0,n+2);
a=x,b=y;
c=new int[maxlength][maxlength];
s=new int[maxlength][maxlength];
c1[i]=0;
s1[i]=0;//。。。。。。 //对二维数组c和s中元素进行初始化
}
void LCS::CLCS(int i,int j) const
{
if (i==0||j==0||s[i][j]==0) return;
if (s[i][j]==1)
{
CLCS(i-1,j-1);
cout<<a[i];
}
else
if (s[i][j]==2) CLCS(i-1,j);
else CLCS(i,j-1);
}
void main()
{ int nx,ny;
char *x, *y;
//。。。。。。
LCS (nx,ny,x,y);
//。。。。。。
delete []x;
delete []y;
}

Answer 1

不是我不想帮你，但如果真要改的话，整个程序差不多要重写了……首先你要确定此程序是上网刷题/比赛？还是自学算法知识？如果你有很好的数学功底还可以自学知识，但比赛的话自学是绝对不够的，那需要充分的交流，还有，养成良好的编程风格是一个极其重要的方面，在网上应该可以找到某些大牛的代码集，运气好还有注释版的，可以多多借鉴。下面是一段代码，NetBeans/G++编译通过，你可以尝试改成类结构的。^_^

#include <iostream>

using namespace std;

#define MAXLENGTH 20

// 这是偷懒的部分……不要介意哈
int maxLength[MAXLENGTH + 2][MAXLENGTH + 2];
int preChar[MAXLENGTH + 2][MAXLENGTH + 2];

/*
* 参数说明
* s1：待处理字符串1
* s2：待处理字符串2
* l1：s1长度（不包括字符串结束符'/0'）
* l2：s2长度（不包括字符串结束符'/0'）
*
* 参数中加const的目的是为了保护外部数据，防止因失误而在函数内部改变了本因无需改变的数值。
*/
int LCSLength(const char* s1, const int l1, const char* s2, const int l2) {

/* 尽量不要在for等语句中定义变量，每个函数一开始最好就把需要的变量全部定义好，同时尽量赋予有意义的函数名 */
/* 当然，有时偷点懒是可以的，但你要确保过了几个月后一看到代码就能很快知道这是啥意思 */
int i, j;
/* maxLength用于存放中间数据，意义：maxLength[i][j]表示：s1前i个字符与s2前j个字符的最长子序列长度
* preChar用于存放当前最长子序列是由那一个自序列得来的
* 因本算法特殊性，需要各额外2位的存储空间
*/

/**/
for (i = 0; i <= l1; i++) maxLength[i][0] = 0;
for (j = 0; j <= l2; j++) maxLength[0][j] = 0;
for (i = 0; i <= l1; i++)
for (j = 0; j <= l2; j++) {
/* 如果s1第i个字符与s2第j个字符相同，则更新maxLength[i+1][j+1]存储的最大值，和preChar存放的前缀自序列位置
* 下同
*/
if (s1[i] == s2[j] && maxLength[i + 1][j + 1] < maxLength[i][j] + 1) {
maxLength[i + 1][j + 1] = maxLength[i][j] + 1;
preChar[i + 1][j + 1] = 1;
}
if (maxLength[i + 1][j] < maxLength[i][j]) {
maxLength[i + 1][j] = maxLength[i][j];
preChar[i + 1][j] = 2;
}
if (maxLength[i][j + 1] < maxLength[i][j]) {
maxLength[i][j + 1] = maxLength[i][j];
preChar[i][j + 1] = 3;
}
}

/* 返回最长子序列长度 */
return maxLength[l1][l2];
}

/**
* s1、s2与上同
* i：s1当前字符序号
* j：s2当前字符序号
*
* i、j初始值为各自字符串长度
*/
void LCSOutput(const char* s1, const int i, const char* s2, const int j) {

if (i >= 0 && j >= 0) {

// 由于是逆向输出，所以先递归，后输出
switch (preChar[i][j]) {
case 1:
LCSOutput(s1, i - 1, s2, j - 1);
break;
case 2:
LCSOutput(s1, i - 1, s2, j);
break;
case 3:
LCSOutput(s1, i, s2, j - 1);
break;
default:
break;
}

if (s1[i] == s2[j])
cout << s1[i];
}
}

int main() {

cout << "最长公共子序列长度：" << LCSLength("1234567890", 10, "1358967", 7) << endl;

cout << "最长公共子序列（不确保唯一）：";
LCSOutput("1234567890", 10, "1358967", 7);
cout << endl;

return 0;
}