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

问题描述

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

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

解决方案

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

//求取所有的最长公共子序列
#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;
}

解决方案二：

#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;

}

时间： 2024-08-08 16:11:29

c-动态规划求最长公共子序列，存在多个解时只能输出一个。的相关文章

算法-求助大神：c语言求最长公共子序列问题

问题描述求助大神:c语言求最长公共子序列问题我写的这个能正确求出最长序列元素个数但是输出的最长序列却是乱码,求大神指教.代码如下: #include #include #include #define MAX 101 int Long(char a[],char b[],char result[] ) { int m,n; m=strlen(a); n=strlen(b); int str[MAX][MAX]; int i,j,sum; for(i=0;i<=m;i++) { str[i][

文本比较算法Ⅶ——线性空间求最长公共子序列的Nakatsu算法

在参阅<A Longest Common Subsequence Algorithm Suitable for Similar Text Strings>(Narao Nakatsu,Yahiko Kambayashi,Shuzo Yajima著)后.发现该算法可以利用线性空间求出最长公共子序列.该算法的时间占用O(n(m-p+1)),p为最长公共子序列的长度. 字符串A和字符串B,计算LCS(A,B) 定义一:设M=Len(A),N=Len(B),不妨设M≤N. 定义二:A=a1a2--

动态规划之最长公共子序列

给定两个序列x和y,称z是x和y的公共子序列,如果z既是x的子序列,又是y的子序列:最长的公共子序列称作最长公共子序列LCS(longest common subsequence). 解题思路 (1)LCS的最优子结构设zk是xm和yn的一个LCS,则,如果x和y的最后一个元素相同,则z中去掉最后一个元素之后zk-1仍为xm-1和yn-1的LCS. 如果xm!=yn,若zk!=xm,则z是xm-1和y的一个LCS,若zk!=yn,则z是xm和yn-1的LCS. (2)一个递归解设c[i][j

算法知识之最长公共子序列问题(动态规划)

最近朋友让帮做个关于动态规划的最长公共子序列的问题,翻看以前的笔记并完成该题后,顺便写这样一篇文章,希望对大家有所帮助,同时也帮助自己回顾该知识点. 一.最长公共子序列的定义子序列:若给定序列X={x1,x2,-,xm},则另一序列Z={z1,z2,-,zk},是X的子序列是指存在一个严格递增下标序列{i1,i2,-,ik}使得对于所有j=1,2,-,k有:zj=xij.公共子序列:给定2个序列X和Y,当另一序列Z既是X的子序列又是Y的子序列时,称Z是序列X和Y的公共子序列.最长公共子序列:给

POJ 1159 Palindrome 最长公共子序列的问题

Description A palindrome is a symmetrical string, that is, a string read identically from left to right as well as from right to left. You are to write a program which, given a string, determines the minimal number of characters to be inserted into t

算法系列（五）最长公共子序列（LCS）问题（非连续子序列）的两种解法

最长公共子序列也称作最长公共子串,英文缩写是LCS(Longest Common Subsequence).其定义是:一个序列S,如果分别是两个或多个已知序列的子序列,且是符合此条件的子序列中最长的,则称 S为已知序列的最长公共子序列. 关于子序列的定义通常有两种方式,一种是对子序列没有连续的要求,其子序列的定义就是原序列中删除若干元素后得到的序列.另一种是对子序列有连续的要求,其子序列的定义是原序列中连续出现的若干个元素组成的序列.求解子序列是非连续的最长公共子序列问题是一个十分实用的

第十五章动态规划——最长公共子序列

1.基本概念一个给定序列的子序列就是该给定序列中去掉零个或者多个元素的序列.形式化来讲就是:给定一个序列X={x1,x2,--,xm},另外一个序列Z={z1.z2.--,zk},如果存在X的一个严格递增小标序列<i1,i2--,ik>,使得对所有j=1,2,--k,有xij = zj,则Z是X的子序列.例如:Z={B,C,D,B}是X={A,B,C,B,D,A,B}的一个子序列,相应的小标为<2,3,5,7>.从定义可以看出子序列直接的元素不一定是相邻的. 公共子序列:给定两个

动态规划解最长公共子序列(LCS)问题 (附可打印LCS完整代码)

一.动态规划法经常会遇到复杂问题不能简单地分解成几个子问题,而会分解出一系列的子问题.简单地采用把大问题分解成子问题,并综合子问题的解导出大问题的解的方法,问题求解耗时会按问题规模呈幂级数增加. 为了节约重复求相同子问题的时间,引入一个数组,不管它们是否对最终解有用,把所有子问题的解存于该数组中,这就是动态规划法所采用的基本方法. 二.问题:求两字符序列的最长公共字符子序列(LCS) 问题描述:字符序列的子序列是指从给定字符序列中随意地(不一定连续)去掉若干个字符(可能一个也不去掉)后所形成的

经典算法题每日演练——第四题最长公共子序列

一: 作用最长公共子序列的问题常用于解决字符串的相似度,是一个非常实用的算法,作为码农,此算法是我们的必备基本功. 二:概念举个例子,cnblogs这个字符串中子序列有多少个呢?很显然有27个,比如其中的cb,cgs等等都是其子序列,我们可以看出子序列不见得一定是连续的,连续的那是子串. 我想大家已经了解了子序列的概念,那现在可以延伸到两个字符串了,那么大家能够看出:cnblogs和belong的公共子序列吗? 在你找出的公共子序列中,你能找出最长的公共子