Нахождение номера сравнения в LCS В динамическом программировании
#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.
Я хочу найти общее нет. сравнений и распечатать его с помощью глобальной переменной count. Может ли кто-нибудь помочь мне?
Решение
Это зависит от того, что именно вы считаете в качестве сравнения.
Я предполагаю, что под сравнением вы подразумеваете «сравнение символов в строке». То есть i==0 делает не считать в сравнении. Также сравнивая значения в max не будет считаться сравнением, так как это делает не сравнить символы из строк. Кроме того, я не проверил вашу программу, проверяя, правильно ли то, что вы делаете, — я просто предположу, что это так, и сосредоточусь на вашем реальном вопросе.
При этом единственное сравнение символов происходит в строке:
else if(x[i-1]==y[j-1])
Следовательно, каждый раз, когда вы делаете эту проверку, вы должны увеличивать свой счетчик. Одним из способов сделать это было бы немного реструктурировать ваши ветви (вместо else if Вы могли бы сделать else{ if{x[i-1]==y[j-1]} }, Если вы сделаете это, то вы можете увеличить counter прямо перед, если. Вот так:
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]))
Тогда было бы совершенно очевидно, что каждый раз, когда выполняется сравнение, счетчик увеличивается.
Я не проверил это полностью, и, конечно, возможны и другие способы, но все же я надеюсь, что вы получили грубую идею.
Другие решения
Других решений пока нет …