真哥沉默思考人生 2014-12-12 13:45 采纳率: 0%
浏览 2555
已结题

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

//求取所有的最长公共子序列
不知道代码哪里写错了,也只有一个币能悬赏,希望有空的大神们帮忙看看,纠结好久了不知道怎么改。
#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条回答 默认 最新

  • 真哥沉默思考人生 2014-12-12 13: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;
      }

    评论

报告相同问题?

悬赏问题

  • ¥50 树莓派安卓APK系统签名
  • ¥15 maple软件,用solve求反函数出现rootof,怎么办?
  • ¥65 汇编语言除法溢出问题
  • ¥15 Visual Studio问题
  • ¥20 求一个html代码,有偿
  • ¥100 关于使用MATLAB中copularnd函数的问题
  • ¥20 在虚拟机的pycharm上
  • ¥15 jupyterthemes 设置完毕后没有效果
  • ¥15 matlab图像高斯低通滤波
  • ¥15 针对曲面部件的制孔路径规划,大家有什么思路吗