-1 
#include<iostream>
#include<string.h>
int count=0;

using namespace std;


int max(int a,int b)
{
    return (a>b)?a:b;
}

int lcs(char *x,char*y ,int m,int n)
{

    int l[m+1][n+1];
    int i,j;

    for( i=0;i<=m;i++)
    {
     for(j=0;j<=n;j++)
        {

        if(i==0 || j==0)
        l[i][j]=0;

        else if(x[i-1]==y[j-1]) 
        l[i][j]=l[i-1][j-1]+1;

        else
        l[i][j] =max(l[i-1][j], l[i][j-1]);

        }
    }


    return l[m][n];


}


int main()
{

    char x[]="AGGTAB";
    char y[]="GXTXAYB";

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

    cout<<"The Length Of the Longest Common Subsequence Is  :   "<<lcs(x,y,m,n);
}

上述程序用于使用动态规划找到最大公共子序列解决方案。我能够计算 LCS 的长度，但我无法推断找到总数的逻辑。系统将进行比较以找到 lcs 。

我想找到总数。比较并使用全局计数变量打印它。有人可以帮我吗？

4

1 回答 1

0

这取决于您将什么视为比较。

我假设，通过比较你的意思是“比较字符串中的字符”。即i==0不算作比较。此外，比较 中的值max也不算作比较，因为它不比较字符串中的字符。另外，我没有通过你的程序检查你所做的是否真的正确——我只是假设它是正确的，并专注于你的实际问题。

话虽这么说，正在发生的字符的唯一比较是在该行中：

else if(x[i-1]==y[j-1])

因此，每次执行此检查时，都应该增加计数器。做到这一点的一种方法是稍微重组你的分支（而不是else if你可以做一个else{ if{x[i-1]==y[j-1]} }. 如果你这样做，那么你可以counter在 if 之前增加右边。像这样：

if(){

}else{ 
 counter++;
 if{x[i-1]==y[j-1]} 

 }else{

 }
}

另一种更明确的方法是让一个函数在那里进行检查和增量。就像是：

bool compareChars(char &first, char &second){
 counter++;
 return first == second;
}

然后你会这样做：

else if(compareChars(x[i-1], y[j-1]))

那么很明显，每次进行比较时，计数器都会递增。

我没有对此进行彻底的测试，当然其他方法也是可能的，但我仍然希望你能大致了解一下。

于 2015-10-16T09:06:03.967 回答