Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: 018 Radacina  (Citit de 10936 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
dushmi
Nu mai tace
*****

Karma: 130
Deconectat Deconectat

Mesaje: 472



Vezi Profilul
« : Mai 29, 2012, 21:42:57 »

Aici puteţi discuta despre problema Radacina.
Memorat
andreifirst
Strain
*

Karma: 4
Deconectat Deconectat

Mesaje: 26



Vezi Profilul
« Răspunde #1 : Mai 29, 2012, 21:48:10 »

Testul 9 are ceva mai special? Caz particular?
Memorat
klamathix
Echipa infoarena
Nu mai tace
*****

Karma: 733
Deconectat Deconectat

Mesaje: 1.216



Vezi Profilul
« Răspunde #2 : Mai 29, 2012, 21:51:39 »

Nu. Ca fapt divers, cand faci cautare binara pe numere reale si urmaresti o anumita precizie, incearca sa faci un numar fix de iteratii, suficient de mare incat sa obtii precizia dorita. Gen eu aici am exact 50 de iteratii si nu ma joc cu niciun eps  Smile Sa-mi spui daca nu rezolvi.
Memorat
darkseeker
De-al casei
***

Karma: 29
Deconectat Deconectat

Mesaje: 106



Vezi Profilul
« Răspunde #3 : Mai 29, 2012, 22:06:45 »

Cum pot determina un interval pe care functia este strict monotona ? Adica eu ma bazam pe faptul ca solutia e intr-un interval de forma [k,k + 1] ,determinam acest interval vazand in ce puncte intregi consecutive functia schimba semnul si iteram fiecare numar din acest interval cu o precizie de 10 ^ 5. Totusi nu trece testul 8 nicicum .
Memorat
tzipleatud
De-al casei
***

Karma: 104
Deconectat Deconectat

Mesaje: 117



Vezi Profilul
« Răspunde #4 : Mai 29, 2012, 22:20:41 »

Cum pot determina un interval pe care functia este strict monotona ? Adica eu ma bazam pe faptul ca solutia e intr-un interval de forma [k,k + 1] ,determinam acest interval vazand in ce puncte intregi consecutive functia schimba semnul si iteram fiecare numar din acest interval cu o precizie de 10 ^ 5. Totusi nu trece testul 8 nicicum .

Poate te ajuta asta. Eu metoda aceasta am folosit-o, utilizand cautarea binara. Bafta!
Memorat
darkseeker
De-al casei
***

Karma: 29
Deconectat Deconectat

Mesaje: 106



Vezi Profilul
« Răspunde #5 : Mai 29, 2012, 22:28:58 »

Multumesc ! .
Memorat
klamathix
Echipa infoarena
Nu mai tace
*****

Karma: 733
Deconectat Deconectat

Mesaje: 1.216



Vezi Profilul
« Răspunde #6 : Mai 29, 2012, 22:31:27 »

Nu ai nevoie sa gasesti intervalul de care vorbesti. Toata ideea e ca daca ai doua valori left si right astfel incat P(left) < 0 si P(right) > 0 (sau invers) atunci sigur ai o radacina in intervalul [left , right]. Iti iei o valoare X in intervalul asta. Daca P(X) < 0 restrangi intervalul la [X , right] altfel la [left , X] (sau simetriile implicite). Toata ideea e sa-ti mentii tot timpul semne diferite in capete ca sa fii sigur ca ai o solutie in intervalul respectiv. Daca alegi X-ul ca fiind mijlocul intervalului, se restrange super repede Smile.

Daca te gandesti un pic, tu nu urmaresti niciodata o anume radacina. Doar te duci incotro stii ca exista una.

Tot ce mai ramane e sa-ti gasesti valorile left si right initiale. -20 si 20 sunt ok pentru asta.

L.E. Da, in mod nesurprinzator chestia asta are un nume Smile).
Memorat
darren
Client obisnuit
**

Karma: 106
Deconectat Deconectat

Mesaje: 76



Vezi Profilul
« Răspunde #7 : Mai 30, 2012, 08:47:58 »

In concurs am incercat o rezolvare la care cautam din eps in eps, in intervalul (-20, 20), si testam fiecare valoare. eps l-am fixat pe 0.00001, si am luat 3 TLE-uri.
Am incercat dupa sa mai jonglez cu valoarea eps-ului, si se pare ca ia 100 cu 0.00002. Think Ar trebui sa se poata gasi teste pentru care sa ia WA solutia asta.
Probabil s-ar putea rezolva si din limita de timp (am timpul maxim 32ms cu solutia asta, pe cand cu cautarea binara am ~0ms). Cu eps 0.00005 ia WA, deci daca limita ar fi cam 0.01s-0.02s, cred ca ar elimina si aceasta solutie.  Smile
Memorat
klamathix
Echipa infoarena
Nu mai tace
*****

Karma: 733
Deconectat Deconectat

Mesaje: 1.216



Vezi Profilul
« Răspunde #8 : Mai 30, 2012, 11:57:56 »

Da, am vazut ca in arhiva au aparut solutii cu eps. A fost destul de bine calibrata treaba totusi, n-a reusit nimeni sa faca asta in concurs. Si oricum te costa multe puncte sa tot incerci precizii diferite & stuff. Probabil o sa mai modificam testele un pic cand avem timp.
Memorat
SpiderMan
Nu mai tace
*****

Karma: -463
Deconectat Deconectat

Mesaje: 937



Vezi Profilul
« Răspunde #9 : Mai 30, 2012, 14:34:31 »

Eu in concurs am facut cu eps = 1e-10 si am luat punctaj maxim Smile.
Memorat
dushmi
Nu mai tace
*****

Karma: 130
Deconectat Deconectat

Mesaje: 472



Vezi Profilul
« Răspunde #10 : Mai 30, 2012, 14:56:56 »

Eu in concurs am facut cu eps = 1e-10 si am luat punctaj maxim Smile.

Ei discutau despre solutia in care parcurgi pas cu pas fiecare numar dintre -20 si 20, nu despre solutia in care faci cautare binara Neutral.

Ontopic: O sa modific eu testele Smile. Nu m-am gandit ca va lua cineva din 2 in 2 Very Happy.
Memorat
SpiderMan
Nu mai tace
*****

Karma: -463
Deconectat Deconectat

Mesaje: 937



Vezi Profilul
« Răspunde #11 : Mai 30, 2012, 15:04:07 »

Poti sa le modifici.
PS : Poti testa solutia cu wolfram alpha Smile.
Memorat
MciprianM
Nu mai tace
*****

Karma: 87
Deconectat Deconectat

Mesaje: 324



Vezi Profilul
« Răspunde #12 : Mai 30, 2012, 15:57:57 »

Nu ai nevoie sa gasesti intervalul de care vorbesti. Toata ideea e ca daca ai doua valori left si right astfel incat P(left) < 0 si P(right) > 0 (sau invers) atunci sigur ai o radacina in intervalul [left , right]. Iti iei o valoare X in intervalul asta. Daca P(X) < 0 restrangi intervalul la [X , right] altfel la [left , X] (sau simetriile implicite). Toata ideea e sa-ti mentii tot timpul semne diferite in capete ca sa fii sigur ca ai o solutie in intervalul respectiv. Daca alegi X-ul ca fiind mijlocul intervalului, se restrange super repede Smile.

Daca te gandesti un pic, tu nu urmaresti niciodata o anume radacina. Doar te duci incotro stii ca exista una.

Tot ce mai ramane e sa-ti gasesti valorile left si right initiale. -20 si 20 sunt ok pentru asta.

L.E. Da, in mod nesurprinzator chestia asta are un nume Smile).

De ce -20 si 20 sunt ok ca valori initiale? Pt polinomul P (x) = (x-1) * (x - 2) vom avea P (-20) > 0 si P (20) > 0. Cum gasim valorile initiale?
Memorat
dushmi
Nu mai tace
*****

Karma: 130
Deconectat Deconectat

Mesaje: 472



Vezi Profilul
« Răspunde #13 : Mai 30, 2012, 16:28:12 »

De ce -20 si 20 sunt ok ca valori initiale? Pt polinomul P (x) = (x-1) * (x - 2) vom avea P (-20) > 0 si P (20) > 0. Cum gasim valorile initiale?

Tocmai din aceasta cauza gradul este impar. Pentru polinoamele de grad par limita la -inf si la inf este egala, pe cand la cele de grad impar cele doua limite sunt diferite.
Memorat
darkseeker
De-al casei
***

Karma: 29
Deconectat Deconectat

Mesaje: 106



Vezi Profilul
« Răspunde #14 : Mai 30, 2012, 16:32:53 »

Eu cred ca valorile acelea sunt bune deoarece se garanteaza ca intre ele exista o solutie . Poti lua un polinom de grad 3 de exemplu x ^ 3 + 2 x ^ 2 + x + 10000 , pentru care atat p(-20) cat si p(20) sunt pozitive .
Memorat
dushmi
Nu mai tace
*****

Karma: 130
Deconectat Deconectat

Mesaje: 472



Vezi Profilul
« Răspunde #15 : Mai 30, 2012, 16:42:51 »

Eu cred ca valorile acelea sunt bune deoarece se garanteaza ca intre ele exista o solutie . Poti lua un polinom de grad 3 de exemplu x ^ 3 + 2 x ^ 2 + x + 10000 , pentru care atat p(-20) cat si p(20) sunt pozitive .

In problema se garanteaza faptul ca toate radacinile sunt in intervalul (-20, 20) de unde rezulta ca pentru x <= -20 si pentru x >= 20 sigur nu mai este taiata axa Ox. Tinand cont si de faptul ca semnele limitelor la -inf si +inf sunt contrare (G impar) => semnul lui P(x) pentru x <= -20 este diferit de semnul lui P(x) pentru x >= 20, adica fix ceea ce ne trebuie (2 puncte, -20 si 20, pentru care semnele cu siguranta sunt contrare).
Memorat
MciprianM
Nu mai tace
*****

Karma: 87
Deconectat Deconectat

Mesaje: 324



Vezi Profilul
« Răspunde #16 : Mai 30, 2012, 16:59:45 »

Multumesc, am inteles.
Memorat
ctlin04
Nu mai tace
*****

Karma: 23
Deconectat Deconectat

Mesaje: 207



Vezi Profilul
« Răspunde #17 : Iunie 03, 2012, 12:05:17 »

Ajutati-ma va rog cu testul 2, iau NON ZERO EXIT STATUS si deja le-am incercat pe toate, se pare ca e o problema la citire din fisier deoarece cind exclud totul si ramine doar citirea da aceeasi eroare Brick wall Brick wall
« Ultima modificare: Iunie 03, 2012, 12:23:09 de către catalin » Memorat
SpiderMan
Nu mai tace
*****

Karma: -463
Deconectat Deconectat

Mesaje: 937



Vezi Profilul
« Răspunde #18 : Iunie 03, 2012, 14:28:12 »

Testele sunt bune, din cate mi se pare la Pascal cred ca eroarea aia vine de la o impartire la 0. Citeste mesajele de eroare de pe IA si vezi.
Memorat
paunmatei7
Strain
*

Karma: 28
Deconectat Deconectat

Mesaje: 27



Vezi Profilul
« Răspunde #19 : Septembrie 11, 2012, 08:38:16 »

Nu inteleg fac la fel cum scrie in solutie si iau la 5 teste TLE.Ma ajutati va rog Very Happy
Memorat
visanr
Nu mai tace
*****

Karma: 168
Deconectat Deconectat

Mesaje: 213



Vezi Profilul
« Răspunde #20 : Septembrie 11, 2012, 09:25:56 »

In primul rand, nu te folosesti de faptul ca trebuie sa ai semne diferite la capetele unui interval (in cautarea binara). In al doilea rand, daca vrei sa vezi daca p e un numar natural (in cazul nostru sa fie 0), trebuie sa iti alegi o precizie (sa zicem 0.0001) pt a elimina erorile de precizie.
Memorat
Mihai22e
Client obisnuit
**

Karma: 20
Deconectat Deconectat

Mesaje: 74



Vezi Profilul
« Răspunde #21 : Iulie 04, 2013, 15:18:49 »

Daca am un polinom in care P(-20) > 0, P(20) > 0 si P(0) > 0, de unde stiu in ce directie sa ma duc dup'aia? Am reusit sa fac problema, dar nu-mi dau seama cum merge pe acest caz.  Smile
Memorat
PlayLikeNeverB4
Nu mai tace
*****

Karma: 212
Deconectat Deconectat

Mesaje: 721



Vezi Profilul
« Răspunde #22 : Iulie 04, 2013, 15:45:26 »

In cazul asta nu cred ca are importanta in ce directie o iei, fiindca exista in ambele parti cel putin o solutie. Uita-te la graficele polinoamelor de grad impar: http://www.purplemath.com/modules/polyends.htm.
Memorat
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines