2 u010589037 u010589037 于 2014.12.12 21:45 提问

动态规划求最长公共子序列,存在多个解时只能输出一个。 1C

//求取所有的最长公共子序列
不知道代码哪里写错了,也只有一个币能悬赏,希望有空的大神们帮忙看看,纠结好久了不知道怎么改。
#include
using namespace std;

const int X=100, Y= 100; //串的最大长度
char result[X+1]; //用于保存结果
int count= 0; //用于保存公共最长公共子串的个数

/*功能:计算最优值
*参数:

  • x:字符串x
  • y:字符串y
  • b:标志数组
  • xlen:字符串x的长度
  •    ylen:字符串y的长度
    

    返回值:最长公共子序列的长度
    *
    */
    int Lcs_Length(string x, string y, int b[][Y+1],int xlen,int ylen)
    {
    int i= 0;
    int j= 0;
    int c[X+1][Y+1];
    /

    • 下面两个for循环将第一行和第一列全置为0
      */
      for (i = 0; i<=xlen; i++)
      {
      c[i][0]=0;
      }

      for (i = 0; i <= ylen; i++ )
      {
      c[0][i]=0;
      }

    for (i = 1; i <= xlen; i++)
    {

    for (j = 1; j <= ylen; j++)
    {
    if ( x[i-1] == y[j-1] )
    {
    c[i][j] = c[i-1][j-1]+1;
    b[i][j] = 1;
    }
    else // c[i][j] = max( c[i-1][j] , c[i][j-1] )
    {
    if ( c[i-1][j] > c[i][j-1] )
    {
    c[i][j] = c[i-1][j]; // 向上
    b[i][j] = 2;
    }
    else
    {
    if( c[i-1][j] < c[i][j-1] )
    {
    c[i][j] = c[i][j-1]; // 向左
    b[i][j] = 3;
    }
    }
    }
    }
    }
    cout << "计算最优值效果图如下所示:" << endl;
    for(i = 1; i <= xlen; i++)
    {
    for(j = 1; j<=ylen; j++)
    {
    cout << c[i][j] << " ";
    }
    cout << endl;
    }
    return c[xlen][ylen]; // 最长公共子序列的长度
    }

    /*功能:计算最长公共子序列
    *参数:

  •    xlen:字符串x的长度
    
  •    ylen:字符串y的长度
    
  •    x    :字符串x
    
  •    b:标志数组
    
  •    current_len:当前长度
    
  •    lcs_max_len:最长公共子序列长度
    

    *
    */
    void Display_Lcs(int i, int j, string x, int b[][Y+1],int current_len,int lcs_max_len)
    {
    if (i ==0 || j==0) //如果到达了边界,则可以输出该序列
    {
    for(int s=0; s < lcs_max_len; s++)
    {
    cout << result[s];
    }
    cout<<endl;
    count++; // 最长公共子串个数加1
    return;
    }

    if(b[i][j] == 1) //情况1: x[i-1] == y[j-1]
    {
    current_len--;
    result[current_len]=x[i- 1];
    Display_Lcs(i-1, j-1, x, b,current_len,lcs_max_len);
    }
    else
    {
    if(b[i][j] == 2) // c[i-1][j]
    {
    Display_Lcs(i-1, j, x, b,current_len,lcs_max_len);
    }
    else
    {
    // c[i][j-1]

    Display_Lcs(i, j-1, x, b,current_len,lcs_max_len);

    }
    }
    }

    int main(int argc, char* argv[])
    {
    string x = "ABCBDABDC";
    string y = "BDCABAC";

    int xlen = x.length();

    int ylen = y.length();

    int b[X+1][Y+1];

    int lcs_max_len = Lcs_Length( x, y, b, xlen,ylen );
    cout << lcs_max_len << endl;

    Display_Lcs( xlen,ylen, x, b, lcs_max_len, lcs_max_len );
    cout << "共有:" << count << "种";
    return 0;
    }

2个回答

u010589037
u010589037   2014.12.12 21:48

代码再发一遍,上面的有点问题。

//求取所有的最长公共子序列
#include
using namespace std;

const int X=100, Y= 100; //串的最大长度
char result[X+1]; //用于保存结果
int count= 0; //用于保存公共最长公共子串的个数

/*功能:计算最优值
*参数:

  • x:字符串x
  • y:字符串y
  • b:标志数组
  • xlen:字符串x的长度
  •    ylen:字符串y的长度
    

    返回值:最长公共子序列的长度
    *
    */
    int Lcs_Length(string x, string y, int b[][Y+1],int xlen,int ylen)
    {
    int i= 0;
    int j= 0;
    int c[X+1][Y+1];
    /

    • 下面两个for循环将第一行和第一列全置为0
      */
      for (i = 0; i<=xlen; i++)
      {
      c[i][0]=0;
      }

      for (i = 0; i <= ylen; i++ )
      {
      c[0][i]=0;
      }

    for (i = 1; i <= xlen; i++)
    {

    for (j = 1; j <= ylen; j++)
    {
    if ( x[i-1] == y[j-1] )
    {
    c[i][j] = c[i-1][j-1]+1;
    b[i][j] = 1;
    }
    else // c[i][j] = max( c[i-1][j] , c[i][j-1] )
    {
    if ( c[i-1][j] > c[i][j-1] )
    {
    c[i][j] = c[i-1][j]; // 向上
    b[i][j] = 2;
    }
    else
    {
    if( c[i-1][j] < c[i][j-1] )
    {
    c[i][j] = c[i][j-1]; // 向左
    b[i][j] = 3;
    }
    }
    }
    }
    }
    cout << "计算最优值效果图如下所示:" << endl;
    for(i = 1; i <= xlen; i++)
    {
    for(j = 1; j<=ylen; j++)
    {
    cout << c[i][j] << " ";
    }
    cout << endl;
    }
    return c[xlen][ylen]; // 最长公共子序列的长度
    }

    /*功能:计算最长公共子序列
    *参数:

  •    xlen:字符串x的长度
    
  •    ylen:字符串y的长度
    
  •    x    :字符串x
    
  •    b:标志数组
    
  •    current_len:当前长度
    
  •    lcs_max_len:最长公共子序列长度
    

    *
    */
    void Display_Lcs(int i, int j, string x, int b[][Y+1],int current_len,int lcs_max_len)
    {
    if (i ==0 || j==0) //如果到达了边界,则可以输出该序列
    {
    for(int s=0; s < lcs_max_len; s++)
    {
    cout << result[s];
    }
    cout<<endl;
    count++; // 最长公共子串个数加1
    return;
    }

    if(b[i][j] == 1) //情况1: x[i-1] == y[j-1]
    {
    current_len--;
    result[current_len]=x[i- 1];
    Display_Lcs(i-1, j-1, x, b,current_len,lcs_max_len);
    }
    else
    {
    if(b[i][j] == 2) // c[i-1][j]
    {
    Display_Lcs(i-1, j, x, b,current_len,lcs_max_len);
    }
    else
    {
    // c[i][j-1]

    Display_Lcs(i, j-1, x, b,current_len,lcs_max_len);

    }
    }
    }

    int main(int argc, char* argv[])
    {
    string x = "ABCBDABDC";
    string y = "BDCABAC";

    int xlen = x.length();

    int ylen = y.length();

    int b[X+1][Y+1];

    int lcs_max_len = Lcs_Length( x, y, b, xlen,ylen );
    cout << lcs_max_len << endl;

    Display_Lcs( xlen,ylen, x, b, lcs_max_len, lcs_max_len );
    cout << "共有:" << count << "种";
    return 0;
    }

devmiao
devmiao   Ds   Rxr 2014.12.13 00:36

#include
#include
#define MAXLEN 100

void LCSLength(char *x, char *y, int m, int n, int c[][MAXLEN], int b[][MAXLEN])
{
int i, j;

for(i = 0; i <= m; i++)
    c[i][0] = 0;
for(j = 1; j <= n; j++)
    c[0][j] = 0;
for(i = 1; i<= m; i++)
{
    for(j = 1; j <= n; j++)
    {
        if(x[i-1] == y[j-1])
        {
            c[i][j] = c[i-1][j-1] + 1;
            b[i][j] = 0;
        }
        else if(c[i-1][j] >= c[i][j-1])
        {
            c[i][j] = c[i-1][j];
            b[i][j] = 1;
        }
        else
        {
            c[i][j] = c[i][j-1];
            b[i][j] = -1;
        }
    }
}

}

void PrintLCS(int b[][MAXLEN], char *x, int i, int j)
{
if(i == 0 || j == 0)
return;
if(b[i][j] == 0)
{
PrintLCS(b, x, i-1, j-1);
printf("%c ", x[i-1]);
}
else if(b[i][j] == 1)
PrintLCS(b, x, i-1, j);
else
PrintLCS(b, x, i, j-1);
}

int main(int argc, char **argv)
{
char x[MAXLEN] = {"ABCBDAB"};
char y[MAXLEN] = {"BDCABA"};
int b[MAXLEN][MAXLEN];
int c[MAXLEN][MAXLEN];
int m, n;

m = strlen(x);
n = strlen(y);

LCSLength(x, y, m, n, c, b);
PrintLCS(b, x, m, n);

return 0;

}

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!