Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?

Nie działąjący algorytm znajdywania najdłuższego wspólnego podciągu

Ostatnio zmodyfikowano 2021-11-11 23:46
Autor Wiadomość
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:
C/C++
#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;
}
P-179054
pekfos
» 2021-11-11 22:55:05
Jaki błąd?
P-179055
Mariusz_99
Temat założony przez niniejszego użytkownika
» 2021-11-11 23:07:18
złe wyniki
P-179056
pekfos
» 2021-11-11 23:46:55
Podobny algorytm jest tu, ale u Ciebie drugi etap jest dużo prostszy.
https://en.wikipedia.org/wiki/Longest_common_subsequence_problem#Reading_out_a_LCS
Jeśli to nie pomoże, podaj przykład danych dla których dostajesz błędny wynik.
P-179057
« 1 »
  Strona 1 z 1