Titlul: 1110 Sortari2 Scris de: Andrei Parvu din Februarie 28, 2011, 01:24:01 Aici puteti discuta despre problema Sortari2 (http://infoarena.ro/problema/sortari2).
Titlul: Răspuns: 1110 Sortari2 Scris de: Vlad Eugen Dornescu din Februarie 28, 2011, 14:01:53 Nu ma prind cum e recurenta pentru :
dp[ i ][ j ] - numarul de permutari de lungime i cu j inversiuni. dp[ i ][ j ] = dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2] + ... dp[i - 1][k] cu k <= j cumva ? L.E : Sau e dp[ i ][ j] += i * dp[i - 1][ j ] + dp[ i - 1][ j - 1 ] ? Titlul: Răspuns: 1110 Sortari2 Scris de: Dragos-Alin Rotaru din Februarie 28, 2011, 15:57:46 Eu am facut dp[ i ][ j ] = numarul de permutari cu proprietatea ceruta astfel incat sa ai i elemente in permutare care incep cu numarul j.
Titlul: Răspuns: 1110 Sortari2 Scris de: Vlad Eugen Dornescu din Februarie 28, 2011, 17:13:50 Am gasit o rezolvare cu dinamica aia pe care am spus-o, cu inversiunile, dar nu stiu inca daca e corecta vreuna din recurentele de mai sus. :)
Titlul: Răspuns: 1110 Sortari2 Scris de: Vlad Eugen Dornescu din Martie 02, 2011, 17:45:00 Sunt curios de ce rezolvarea cu fibonacci este asa cum este.
Poate explica cineva ? :) Titlul: Răspuns: 1110 Sortari2 Scris de: Filip Cristian Buruiana din Martie 05, 2011, 00:30:57 Numarul de permutari cu timp de sortare egal prin cele doua procedee si care incep cu 1 este fib[2N-3], numarul celor care incep cu 2 este tot fib[2N-3], numarul celor care incep cu 3 este fib[2N-5], cu 4 fib[2N-7]. Avem ca:
Cod: fib[1] + fib[3] + fib[5] + … + fib[2N-5] + fib[2N-3] + fib[2N-3] = Demonstratia se face prin inductie. Cand la o permutare cu N elemente adaugam 1 in fata nu se schimba nimic => numarul permutarilor cu N+1 elemente care incep cu 1 este fib[2N-1]. Cand la o permutare cu N elemente adaugam 2 in fata (crescand cu 1 elementele >= 2), evident numarul inversiunilor creste cu 1 si la fel si numarul ciclurilor => adaugam fib[2N-1] la solutie. Cand adaugam x (x >= 3), permutarea trebuie sa inceapa astfel: x 1 2 … (x-2) P, unde P este o permutare de lungime N-x+2 care trebuie sa aiba propr. ceruta. Numarul permutarilor P este din ipoteza inductiva fib[2*(N-x+2)-1] = fib[2N-2x+3]. Pentru x = 3, 4, 5.. sumam valori de forma fib[2N-3], fib[2N-5], etc si ajungem in final la o suma de forma: fib[1] + fib[3] + … + fib[2N-5] + fib[2N-3] + fib[2N-1] + fib[2N-1] = fib[2N+1], ceea ce trebuia demonstrat. Titlul: Răspuns: 1110 Sortari2 Scris de: Vlad Eugen Dornescu din Martie 05, 2011, 08:55:01 Multumesc.Totusi, egalitatile cu fib[2n - 3] pt cele care incep cu 1, fib[2n - 3] pt cele de lungime n care incep cu 2, fib[2n - 5] pt cele de lungime n care incep cu 3 etc. sunt observatii?
Sau are vreo teoretic vreo legatura sirul fibonacci cu ciclul intr-o permutare? Titlul: Răspuns: 1110 Sortari2 Scris de: Filip Cristian Buruiana din Martie 05, 2011, 12:33:46 Dupa ce am observat regulile de formare, eu am demonstrat inductiv ca mai sus. Nu stiu daca are legatura cu ciclurile intr-o permutare in general :)
|