•XamWaZ
Strain
Karma: -1
Deconectat
Mesaje: 8
|
|
« : Martie 13, 2012, 17:02:03 » |
|
Am o problema care imi da batai de cam de 3 zile. Se da un sir de n numere intregi. Sa se toreasca spre stanga cu k pozitii fara a se folosi un sir suplimentar. exemplu: [1,2,3,4,5,6,7] rotire cu 3 pozitii -> [4,5,6,7,1,2,3]. Si ca indicatie am sa nu fac k rotiri a cate un element deoarece e ineficient.
Am tot incercat sa gasesc un algoritm, insa nu am reusit doar pe cazuri particulare.
|
|
|
Memorat
|
|
|
|
•gabitzish1
|
|
« Răspunde #1 : Martie 13, 2012, 17:15:28 » |
|
Ca sa rotesti un sir cu K pozitii la stanga poti face asa: - inversezi pozitiile 1 -> K => K, K-1, ..., 1, K+1, K+2, ..., N
- inversezi pozitiile K+1 -> N => K, K-1, ..., 1, N, N-1 ..., K+1
- inversezi tot sirul => K+1, K+2, ..., N, 1, ..., K
|
|
|
Memorat
|
|
|
|
•klamathix
|
|
« Răspunde #2 : Martie 13, 2012, 21:35:50 » |
|
Sau poti sa mai concatenezi sirul inca o data la sfarsit 1 2 3 4 5 6 7 1 2 3 4 5 6 7
Acum orice rotatie a sirului initial este o subsecventa de lungime N al acestui sir.
L.E @Gabi Dap, scuze. N-am vazut.
|
|
« Ultima modificare: Martie 13, 2012, 21:47:48 de către Mihai Calancea »
|
Memorat
|
|
|
|
•gabitzish1
|
|
« Răspunde #3 : Martie 13, 2012, 21:45:00 » |
|
Se da un sir de n numere intregi. Sa se toreasca spre stanga cu k pozitii fara a se folosi un sir suplimentar.
Concatenand sirul la sfarsit mi se pare ca se foloseste un fel de sir suplimentar
|
|
|
Memorat
|
|
|
|
•SpiderMan
|
|
« Răspunde #4 : Martie 13, 2012, 21:46:17 » |
|
Poti sa nu faci asta cu concatenarea, faci tot pe sirul V, te duci cu primul for de la K + 1 pana la N, si apoi de la 1 -> K .
|
|
|
Memorat
|
|
|
|
•XamWaZ
Strain
Karma: -1
Deconectat
Mesaje: 8
|
|
« Răspunde #5 : Martie 13, 2012, 21:48:05 » |
|
pai e ca si cu un sir suplimentar asa. @SpiderMan cum zici tu e doar parcurgerea. eu nu vreau sa il parcurg ci sa ii rotesc elementele. la final daca afisez tot sirul sa am elementele rotite.
cum zicea gabitzish1 am gasit si eu o solutie, insa nu prea am inteles cum ziceai acolo. tot interschimband valorile repetat din k in k pana ajungi de unde ai pornit e cea mai optima solutie.
|
|
|
Memorat
|
|
|
|
•gabitzish1
|
|
« Răspunde #6 : Martie 13, 2012, 21:57:54 » |
|
Nu stiu cum sa'ti explic mai pe inteles... faci reverse la subsecventa [1 -> K], reverse la subsecventa [K+1 -> N], si reverse la tot sirul apoi (subsecventa [1 -> N]);
|
|
|
Memorat
|
|
|
|
•SpiderMan
|
|
« Răspunde #7 : Martie 13, 2012, 21:59:33 » |
|
Pai faci ce-o zis Mihai, doar faci cum am zis eu, in loc de pozitia N + 1 .... 2N pui pozitiile din sirul initial , teoretic nu e un sir suplimentar, ca nu-l declari (daca la asta se refera). [LE] Cum a zis gabitzish1, e foarte bine si asa, ai chiar o functie in STL reverse care face asta lejer .
|
|
|
Memorat
|
|
|
|
•XamWaZ
Strain
Karma: -1
Deconectat
Mesaje: 8
|
|
« Răspunde #8 : Martie 13, 2012, 22:04:48 » |
|
@gabitzish1, acum am inteles, cred ca e cel mai simplu asa, la complexitate e la fel ca solutia care am gasit-o ultima data, ca se fac n interschimbari.
@SpiderMan cum zici tu inca raman pe pozitiile 1..k elemente care mie nu imi trebuie si cam sa le sterg trebuie facuti mai multi pasi si deja devine ineficient.
|
|
|
Memorat
|
|
|
|
•laurion
|
|
« Răspunde #9 : Martie 13, 2012, 22:16:26 » |
|
merge si cu hash-uri
|
|
|
Memorat
|
|
|
|
•wefgef
|
|
« Răspunde #10 : Martie 13, 2012, 23:40:50 » |
|
merge si cu hash-uri Nu prea.
|
|
|
Memorat
|
omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
|
|
|
•laurion
|
|
« Răspunde #11 : Martie 13, 2012, 23:51:39 » |
|
ouch scuze, nu am citit bine, credeam ca trebuie aflat daca un sir e rotirea altuia, asa mergea cu hash-uri...
|
|
|
Memorat
|
|
|
|
•Fayed
Client obisnuit
Karma: -24
Deconectat
Mesaje: 62
|
|
« Răspunde #12 : Aprilie 06, 2012, 21:06:06 » |
|
Poti face permutari circulare la dreapta de k ori. iata codul: for(int i=1;i<=k;++i) { aux=V[n]; for(int j=2;j<=n;++j) { V[1]=aux; V[j]=V[j-1]; } }
complexitatea este insa de O(n*k)
|
|
|
Memorat
|
|
|
|
•Fayed
Client obisnuit
Karma: -24
Deconectat
Mesaje: 62
|
|
« Răspunde #13 : Aprilie 06, 2012, 21:09:21 » |
|
la stanga nu le dreapta. Scuze! Greseala mea.
|
|
|
Memorat
|
|
|
|
|