在LCS中查找比較數量在動態編程中

-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。在LCS中查找比較數量在動態編程中

我想找到總的沒有。的比較，並使用全局計數變量進行打印。有人可以幫我嗎？

來源

2015-10-15 Namit Pathak

這取決於你算什麼作爲比較。

我認爲，通過比較你的意思是「比較字符串中的字符」。即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]))

然後它會非常明顯，每次比較完成後計數器就會增加。

我沒有徹底地測試這個，當然其他方法也是可能的，但我希望你能得到大概的想法。

來源

2015-10-16 09:06:03 dingalapadum

我想統計它將採取的cpu comaparision？ –

@NamitPathak：你將不得不在其他地方增加。就像for循環一樣。再次，您可以創建一個附加函數並將其放入循環條件中，如下所示：'for（int i = 0; leq（i，m）; i ++）'。函數'leq'（小於或等於）將增加計數器，然後返回一個bool，無論比較結果是否爲真。同樣，對於'i == 0'，你將需要像'isZero（i）'這樣的東西。你還需要在'max'中增加。實際上，您需要用首先增加計數器然後進行比較的函數來替換*全部*比較。 – dingalapadum

@NamitPathak：如果你想計算*所有* cpu比較，它會變得更毛茸茸。我不太清楚如何計算像cout這樣的庫函數中的比較。我會嘗試的是：靜態編譯程序（'-static'），然後用'-S'標誌來查看程序集。然後查找所有的指令，比較它們並在每個指令之前遞增計數。但我對此不太確定。無論如何，我認爲這是一個更廣泛的問題，可能值得獨立於問題自己的問題和答案。你想問嗎？或者我應該這樣做？ – dingalapadum

在LCS中查找比較數量在動態編程中

回答

相關問題