Imprimă pagina - problema dinamica

Titlul: problema dinamica
Scris de: Alexandru Valeanu din Aprilie 05, 2013, 10:36:12

Am gasit o problema de dinamica pe campion: http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=616

Citat

Fie A si B doua siruri formate din maxim 1000 litere mici ale alfabetului englez.

Un subsir al unui sir este format din caractere (nu neaparat consecutive) ale sirului respectiv, în ordinea în care acestea apar în sir.

Cerinta

Scrieti un program care sa determine cel mai scurt subsir al sirului A, care nu este subsir al sirului B.

Stiu relatia de recurenta la cel mai lung subsir comun dar nu stiu cum sa o adaptez pentru acest caz...

Cod:

for ( int i = 1; i <= lgA; i++ )
        for ( int j = 1; j <= lgB; j++ )
            if ( A[i] != B[j] )
                D[i][j] = D[i - 1][j - 1] + 1;
            else
                D[i][j] = min ( D[i][j - 1], D[i - 1][j] );

Recurenta de mai sus este cea la care m-am gandit dar merge pe majoritatea testelor.

Titlul: Răspuns: problema dinamica
Scris de: Adrian Craciun din Aprilie 05, 2013, 20:53:59

Citat

Recurenta de mai sus este cea la care m-am gandit dar merge pe majoritatea testelor.

wut? esti obosit :P

Cod:

for ( int i = 1; i <= lgA; i++ )
        for ( int j = 1; j <= lgB; j++ )
            if ( A[i] != B[j] )
                D[i][j] = D[i - 1][j - 1] + 1;
            else
                D[i][j] = min ( D[i][j - 1], D[i - 1][j] );

Recurenta ta e complet gresita. Nu merge pur si simplu sa faci pe "invers" cmlsc :)
Ti-am trimis PM

Titlul: Răspuns: problema dinamica
Scris de: George Marcus din Aprilie 05, 2013, 22:29:19

De ce PM? Poate sunt si altii curiosi.

infoarena

infoarena - concursuri, probleme, evaluator, articole => Informatica => Subiect creat de: Alexandru Valeanu din Aprilie 05, 2013, 10:36:12