Поиск числа сравнения в LCS При динамическом программировании

Question

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

Я хочу найти общий номер. сравнений и распечатать его с использованием глобальной переменной счетчика. Может ли кто-нибудь помочь мне?

Answer 1

Это зависит от того, что именно вы считаете в качестве сравнения.

Я предполагаю, что для сравнения вы имеете в виду «сравнение символов в строке». То есть 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])) 

Тогда было бы очень очевидно, что каждый раз, когда выполняется сравнение, счетчик увеличивается.

Я не тщательно тестировал это, и, конечно, возможны другие способы, но я надеюсь, что вы получите приблизительную идею.