infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: Andrei Parvu din Februarie 28, 2011, 01:24:01



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] = 
fib[2] + fib[3] + fib[5] + … + fib[2N-5] + fib[2N-3] + fib[2N-3] =
fib[4] + fib[5] + … + fib[2N-5] + fib[2N-3] + fib[2N-3] =
…………………………………………………………. =
fib[2N-2] + fib[2N-3] = fib[2N-1].

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 :)