262 Free

[ditzone]

Aici puteţi discuta despre problema Free.

[•pocaitu]

 Stie cineva un link unde gasesc operatii cu numere mari , ca la programu meu operatiile astea imi iau o gramada de timp?

[•cos_min]

da : http://info.devnet.ro/articole.php?page=art&art=22&artpage=4

[•pocaitu]

mersi ffff mult cos_min . Intradevar erau cam complicate operatiile mele;  le faceam pe siruri de caractere (char) pt ca puteai sa afli lungimea lor dar se pare ca a fost o prostie.

[•cos_min]

hmm numa 20 pcte iau (restu TLE)... pt sqrt fac o cautare binara si operatiile pe nr mari le folosesc cele din articolul de pe info.devnet.ro
 

[•Coty]

incearca sa extragi radicalul "ca pe foaie"... eu iau 70 pe rezolvarea asta, inca am un mic bug... si complexitate o sa iasa O(Nr cifre)... 

[•pocaitu]

eu fac tot o cautare binara si operatiile de info.devnet  si iau 100

[•cos_min]

hmm dak initializez de fiecare data siru cu memset imi iese din timp shi dak nu ii il initializez nu imi merge ... ce pot face? need help

[•pocaitu]

ca tot veni vorba de memset , stie cineva de ce la mine pe calculator nu merge NICIODATA memset-ul decat atunci cand initializez sirul cu 0 ??

[•greco]

memset-ul seteaza fiecare byte la valoarea pe care i-o dai. Pe un vector de char o sa-ti mearga mereu, dar pe un vector de int se seteaza atat primul cat si cel de-al doilea byte cu valoarea. De exemplu, facand memset(v, 1, sizeof(v)) unde v e char, fiecare element o sa fie egal cu 00000001, iar facand memset(v, 1, sizeof(v)) unde v e int, fiecare element o sa fie egal cu 0000000100000001.

Ma rog... asta daca sizeof(int) = 2. Daca sizeof(int) = 4... o sa apara 00000001 de 4 ori.

[•Cosmin]

Singurele numere care isi pastreaza reprezentarea binara daca sunt dublate sunt -1 si 0 deci iti va merge si memset cu -1 tot timpul

[u-92]

memset(A, 0, sizeof(A)) va merge pe orice platforma daca A este de tipul char. daca A este de tip int sa spunem pot aparea surprize, in sensul ca toate elementele lui A nu vor avea valoarea 0 (zero). nu ar trebui sa fie nicio diferenta intre un for si memset, ba chiar sa mearga mai repede for-ul, insa pe un post mai vechi infoa erau facute niste teste si memset rula mai avantajos ca timp.
asa am auzit eu..   

[•Cosmin]

Daca te refereai ca -1 e intreg, el are aceiasi reprezentare binara 111....111 pe oricati biti ar fi reprezentat, deci cred ca merge pe orice platforma la fel.

[•pocaitu]

acuma m-am lamurit

[•cos_min]

hmm mai mult de 40 pcte nu pot scoate ... 
nush ce sa modific la cautarea binara ... sigur acol ii ceva gresit

[•Cosmin]

Uite aici doua tutoriale despre cautarea binara:
http://www.tbray.org/ongoing/When/200x/2003/03/22/Binary

http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=binarySearch

Eu de cand am citit primul articol nu am mai bushit la cautare binara. Ideea e sa iti fixezi un invariant la inceput si atunci e foarte usor sa scrii codul fara sa te mai concentrezi la chestii de +/- 1 si sa nu fi sigur ce se intampla.

[•cos_min]

10x Cosmin ... mi-o iesit de 100 in sfarsit  [am observat in al 2-lea articol o optimizare, care mo ajutat sa scot pctj maxim]

[•Cosmin]

Ce optimizare ca sunt curios?

[•cos_min]

optimizare : mij=st+(dr-st)/2 .. dak am pus asta in loc de mij = (st+dr)/2 mi-o mers ...

[nivan]

dupa ce am facut cautarea binara, am observat ca implementarea ei pe numere HUGE dar intregi (fara virgula), obtine SQRT-ul doar pentru numerele patrate perfecte. De altfel asa e si logic 25*25 = 625 nu cu 626. Daca caut radical din 626 nu va gasi nimic.

O metdoda de a obtine truncul ar fi sa fac operatiile pe numere mari cu virgula. Dar inainte sa ma omor, poate exista o varianta mai simpla si nu-mi dau eu seama acuma.

Ma corectez... nu merge nici pe numere mari cu virgula

[•pocaitu]

pai pentru fiecare mij vezi daca  (mij*mij <=nr&&(mij+1)*(mij+1)>n)
 atunci mij = sqrt(n)

[nivan]

mersi da deja imi dadusem seama. mersi oricum.

[•Cosmin]

Dubios cos_mine aia nu prea e optimizare ci poate doar schimbare a modului in care scrii codul. O optimizare ar fi sa folosesti in loc de baza 10 o baza de 1000 sau 1000000.
Cat despre ce zice pocaitu nu tre sa faci (mij*mij <=nr&&(mij+1)*(mij+1)>n)
ci:

Cod:

low_end = 0
high_end = 10^100 + 1
 while high_end - low_end > 1 
       mid  = (high_end + low_end) / 2
       if mid * mid <= n
             low_end = mid
         else 
             high_end = mid

write low_end

invariantul aici este ca low_end <= sqrt(n) si high_end > sqrt(n), vedeti ce usor stim ce valoare trebuie sa ii dam lui high_end si low_end dupa o comparatie, si nu mai apare nici un +-1.

[•svalentin]

poate lui cos_min ii dadea overflow..
adica poate st+dr iesea din tipul lui de date.. daca calculezi prin st+(dr-st)/2 nu vad unde poate da overflow
.. oricum, nu e optimizare

[•Cosmin]

Nu prea poti vorbi la overflow la tipuri de date mari .