卡在二維邏輯

嗨我寫了一個最不常見的子序列問題的程序，卡在二維邏輯

並堅持2 dim陣傳遞和遍歷。善意幫助。

以下是一段代碼。

void backtrack(char x[], char y[], int L[][7], int m, int n) 
{ 
    if(m == 0 || n == 0) 
    return; 

    else if(x[m-1] == y[n-1]) 
    { 
    backtrack(x, y, L, m-1, n-1); 
    cout << x[m-1] << " "; 
    } 

    else 
    { 
    if(L[m-1][n] > L[m][n-1]) 
     backtrack(x, y, L, m-1, n); 
    else 
     backtrack(x, y, L, m, n-1); 
    } 
} 


int lcs_length(char x[], char y[], const int m, const int n) 
{ 
    int L[m+1][n+1]; 

    for(int i=0; i<=m; i++) 
    {  
    for(int 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]); 
    }   
    }  
    backtrack(x, y, L, m+1, n+1); 
    return L[m][n]; 
} 



int main(int argc, char *argv[]) 
{ 
    char x[] = "ABCDGH"; 
    char y[] = "AEDFHR"; 

    int m = sizeof x/sizeof *x; 
    int n = sizeof y/sizeof *y; 

    cout << lcs_length(x, y, m, n); 

    return EXIT_SUCCESS; 
}

我基本上停留在呼籲從lcs_length（），因爲我不能夠通過/遍歷走回頭路內的2維數組的回溯功能...

好心幫..

謝謝。

來源

2011-06-21 AGeek

什麼是行int m = sizeof x/sizeof * x; int n = sizeof y/sizeof * y;'打算幹什麼？ –

int m = sizeof x/sizeof * x; int n = sizeof y/sizeof * y; >>計算字符串x，y的長度。在g ++編譯器中執行.. – AGeek

您正在使用C++，但仍然使用c樣式的數組？你應該儘快切換到載體，他們會讓你的生活更輕鬆。立即解決您的問題。 – LiKao

您在lcs_length中的二維數組L不是真正的c數組，因爲您使用變量來設置元素的數量。當設定其大小時，例如到int L[100][7]一切工作正常。

但解決你的問題，我寧願使用一個真正的動態數組，例如：

int **L = new int* [m+1]; 
for (int i = 0; i < m+1; i++) 
    L[i] = new int[n+1];

然後，你可以傳遞數組作爲int ** L。

來源

2011-06-21 09:28:58 Elrohir

卡在二維邏輯

回答

相關問題