|
Titlul: Sortarea prin oglindiri (o problema) Scris de: Nita Iulian din Martie 25, 2013, 18:32:43 Am gasit urmatoarea problema:
Se citeşte de la tastatură un şir de n numere naturale cuprinse între 1 si 60000. Se cere ordonarea crescătoare a acestui şir folosind următoarea operaţie: se fixează un element al şirului şi apoi se oglindesc secvenţele din stânga şi din dreapta lui. De exemplu, dacă în şirul (6 5 7 8 9 4 6 5) se fixează elementul de pe poziţia 4 se va obţine şirul (7 5 6 8 5 6 4 9) adică se oglindeşte şirul (6 5 7) şi şirul (9 4 6 5), şiruri aflate în stânga şi respectiv în dreapta elementului de pe poziţia 4. Se pot fixa şi elementele fictive de pe poziţiile 0 si n+1. Să se afişeze toate poziţiile care s-au fixat pentru a ajunge la soluţie. Numărul acestor poziţii fixate trebuie să nu fie mai mare decât 3n. Exemplu. Pentru şirul (4,20,5,50,25) poziţiile fixate sunt (4,5,5,6,4, 5,5,6,5,6). Asta am lucrat eu pana acum http://pastebin.com/YKSawJze :spiteful: Trebuie sa-mi mai dau seama in ce mod se alege pozitia pentru oglindire ](*,) Titlul: Răspuns: Sortarea prin oglindiri (o problema) Scris de: Avramescu Cristia din Martie 25, 2013, 19:49:42 pot sa te intreb unde ai gasit problema? :)
Titlul: Răspuns: Sortarea prin oglindiri (o problema) Scris de: Nita Iulian din Martie 25, 2013, 20:02:32 Mi-a dat doamna profesoara sa lucrez, dar nici dansa nu stie s-o rezolve... :horsy:
Titlul: Răspuns: Sortarea prin oglindiri (o problema) Scris de: Popa Mihai din Martie 25, 2013, 20:38:48 Cred ca problema este si pe infoarena :):
http://www.infoarena.ro/problema/order2 Titlul: Răspuns: Sortarea prin oglindiri (o problema) Scris de: Nita Iulian din Martie 25, 2013, 20:45:13 Interesant :oops:
Nu stiam , n-am mai intalnit-o. Si totusi, are 0.1 sec limita de timp, merge cat de cat oglindirea facuta de mine ? Sau sunt complet paralel cu problema...? :-' Titlul: Răspuns: Sortarea prin oglindiri (o problema) Scris de: Popa Mihai din Martie 25, 2013, 20:54:47 Solutia problemei e O(n^2). Functia de oglindire e buna dar trebuie sa vezi cum folosesti oglindirile incat sa sortezi sirul. Nu e corecta abordarea ta cu citirea x-ului la care sa oglindesti :-k
Titlul: Răspuns: Sortarea prin oglindiri (o problema) Scris de: Nita Iulian din Martie 25, 2013, 20:59:20 Stiu, am pus chestia cu citirea pozitiei pentru a testa mai rapid exemplele date de mine si sincer sa fiu nici exemplele nu le pot duce pana la capat.. din momemnt ce nu le-am inteles matematic nici n-am ce implementa. (as crede ca trebuie un if ceva.. sa caut o secventa crescatoare/descrescatoare sau nu stiu.... inca n-am gasit o idee care sa mearga pe caz general).
Titlul: Răspuns: Sortarea prin oglindiri (o problema) Scris de: Popa Mihai din Martie 25, 2013, 21:05:08 http://probleme.francu.com/arhiva/R0028/enunt.html
De aici e luata problema, vad ca e si rezolvarea acolo. Bafta! Titlul: Răspuns: Sortarea prin oglindiri (o problema) Scris de: Nita Iulian din Martie 25, 2013, 21:30:37 Multumesc pentru sursa. O sa studiez cu atentie sa vad care-i faza cu pozitiile acelea pe acolo. :weightlift:
|