Nie działąjący algorytm znajdywania najdłuższego wspólnego podciągu
Ostatnio zmodyfikowano 2021-11-11 23:46
Mariusz_99 Temat założony przez niniejszego użytkownika |
Nie działąjący algorytm znajdywania najdłuższego wspólnego podciągu » 2021-11-11 22:39:44 Napisałem dynamiczny algorytm liczący sumę elementów najdłuższego wspólnego podciągu, lecz gdzieś jest błąd, którego od dawna nie mogę znaleźć. Proszę o pomoc. Oto mój kod: #include<iostream> using namespace std; int tab1[ 10000 ]; int tab2[ 10000 ]; int tab[ 100 ][ 1000 ];
int main() { int n; cin >> n; for( int i = 0; i < n; i++ ) cin >> tab1[ i ]; for( int i = 0; i < n; i++ ) cin >> tab2[ i ]; for( int i = 0; i <= n; i++ ) { for( int j = 0; j <= n; j++ ) { if( i == 0 || j == 0 ) tab[ i ][ j ] = 0; else { if( tab1[ i - 1 ] == tab2[ j - 1 ] ) { tab[ i ][ j ] = tab[ i - 1 ][ j - 1 ] + 1; } else tab[ i ][ j ] = max( tab[ i - 1 ][ j ], tab[ i ][ j - 1 ] ); } } } int licznik = 0; int i = n, j = n; while( i >= 0 && j >= 0 ) { if( tab1[ i - 1 ] == tab2[ j - 1 ] ) { licznik += tab1[ i - 1 ]; j--; i--; } else { if( tab[ i - 1 ][ j ] > tab[ i ][ j - 1 ] ) i--; else j--; } } cout << licznik; }
|
|
pekfos |
» 2021-11-11 22:55:05 Jaki błąd? |
|
Mariusz_99 Temat założony przez niniejszego użytkownika |
» 2021-11-11 23:07:18 złe wyniki
|
|
pekfos |
» 2021-11-11 23:46:55 |
|
« 1 » |