|
Titlul: Subsir comun de lungime maxima a 3 siruri Scris de: George Popoiu din Martie 03, 2010, 21:24:43 Din cate imi amintesc cred ca am vazut problema explicata intr-un articol chiar aici pe infoarena, dar asta era cu ceva timp in urma.
Acum cand am nevoie de rezolvarea problemei, nu am reusit sa o mai gasesc si de aceea postez aici. Daca cunoasteti rezolvarea as fi recunoscator daca ati explica-o, sau mai bine, sa ma directionati catre articol. (daca exista) :) Titlul: Răspuns: Subsir comun de lungime maxima a 3 siruri Scris de: Andrei Misarca din Martie 03, 2010, 21:37:13 Cred că merge să ții o dinamică D[ i ][ j ][ k ] -> lungimea celui mai lung subșir comun luând în considerare primele i elemente din primul, primele j din al doilea, și primele k din al treilea.
D[ i ][ j ][ k ] = D[ i-1 ][ j-1 ][ k-1 ] + 1, dacă A[ i ] = B[ j ] = C[ k ]. max(D[ i-1 ][ j ][ k ], D[ i ][ j-1 ][ k ], D[ i ][ j ][ k-1 ]), altfel. Titlul: Răspuns: Subsir comun de lungime maxima a 3 siruri Scris de: George Popoiu din Martie 03, 2010, 21:53:35 M-am gandit si eu la aceasta recurenta si i-am dat niste teste usoare, dar din pacate nu este corect. :-k
Titlul: Răspuns: Subsir comun de lungime maxima a 3 siruri Scris de: Andrei Misarca din Martie 03, 2010, 22:14:35 Eu am implementat dinamica de mai sus și am dat niște teste care se pot face de mână și mi-a dat pe toate. Pune un test pe care nu ți-a dat dinamica.
Titlul: Răspuns: Subsir comun de lungime maxima a 3 siruri Scris de: George Popoiu din Martie 04, 2010, 08:42:28 Da, mi-a mers, cred ca gresisem la implementare, multumesc ! :thumbup:
|