003 Fractii

[•fluffy]

Aici puteţi discuta despre problema Fractii.

[•geag]

Asa ca... La fractii trebui sa fie o formula nu? Yes or no answer please...  

[•domino]

Nu. Si nu mai scrie cu text mare ca nu suntem orbi...

[•geag]

Ok, mersi pentru raspuns. (si amabilitate   )

[VladS]

Am si eu o intrbare ce dimensiune au testele de la problema asta. Eu
mi-am luat 0 cu un algoritm zic eu destul de eficient. Are o comlezitate
<n*n

[•fluffy]

n*n e enorm pentru problema asta.

[•Figure09]

shi totushi... ce complexitate ar trebui sa aiba fractii?   mersi...

[•domino]

O complexitate O(N * lg N) intra in timp.. desigur, poti sa faci si mai putin  :lol:

[•Figure09]

i'm a bit confused.... de unde imi apare mie logN? merg de la 1 la n shi calculez pt fiecare in logN? shi le adun? sec... dar faina problema..

[•domino]

Nu e bine sa spui o complexitate si apoi sa incerci sa-ti imaginezi rezolvarea pornind doar de la complexitate... pur si simplu, incearca sa gasesti o rezolvare care se incadreaza in timp  

[•dinu]

incercati ciurul lui Eratostemos. Merge in NlogN si da faci cum trebuie iese bine. Eu asa am facut de 100 de puncte

[•LordAnta]

ce spune ciurul lui Eratostemos sau unde pot gasi informatii despre continutul ei?

[•domino]

ce spune ciurul lui Eratostemos sau unde pot gasi informatii despre continutul ei?

Ciurul lui Eratostene e o metoda de complexitate O(N*lg N) pentru a determina toate numerele prime <= N. Se invata la mate prin clasa a 5-a cred   . Ideea e sa tii un vector de true sau false si pt fiecare numar i sa marchezi toti multiplii sai <= N ca fiind true. Valorile care raman false vor fi numere prime. Complexitatea este O(N*lg N) fiindca 1/1 + 1/2 + 1/3 + ... + 1/N = O(lg N), iar memoria folosita este O(N). Ca fapt divers s-a demonstrat ca ciurul lui Eratostene are o complexitate Theta(N*lg lg N); de asemenea se poate reduce memoria folosita la O(sqrt(N)), dar asta n-are legatura cu problema  

[•LordAnta]

Ideea cu ciurul lui Eratostene ii foarte interesanta, dar nu stiu cum de s-o ajuns de la Eratostene la Eratostemos. Sarmanul matematician, se invarte in mormant la cat i-am stalcit numele!!! :lol:

[•horax]

http://mathworld.wolfram.com/TotientFunction.html

aici gasiti indicatii.

poate va ajuta la fractii  

[•bogdan2412]

Mircea, poti sa pui te rog un test de la problema asta (mai mic) pe forum. Am trimis nushtu cate rezolvari, cu doua metode total diferite si n-am luat nici un punct. Nu prea inteleg unde gresesc, tot ce am dat eu a mers.

[•silviug]

N -> Rezultat

11 -> 83
15 -> 143
31 -> 615
99 -> 6007
100 -> 6087
1000000 -> 607927104783

Sper sa fi copiat bine
Succes!

Silviu

[•mcbrood]

pana la 1.000.000 sunt 78.498 de numere prime. am scris un algoritm pe baza ca stiu toate cele R numere prime <= N si ca numarul de fractii il memorez intr-un vector de 14 cifre. nuj cum ati facut voi exact dar io am folosit functia totentiala conform formulei rezultat(N)=1+2*(tot(2)+tot(3)+...+tot(N)); functia totentiala intoarce numarul de numere < N si relativ prime la N.
multumesc anticipat

[•silviug]

Suna ceva mai complicat decat este necesar dar e pe aceeasi idee. Totusi, a mers pan la urma ?

[•mcbrood]

nu prea a mers...adik nu am dus-o pana la capat. folosind chestia care am postat-o mai devreme si un algoritm simplu de generare a numerelor prime am aplut vectorul cu numere prime...problema este ca a facut asta in 5,171 sec    .... deci metoda asta pica ... nu era destul de clar post-ul precedent dar era vorba de o intrebare...cat de simplu se poate rezolva problema si cum.ma tot gandesc la chestia cu ciurul lui erastotene si o sa implementez o rezolvare sugerata mai sus cu 0 si 1. ramane insa intrebarea cu memoria, dc fac aja ajung sa folosesc 1 mega de HEAP numai pentru vectorul semafor. mi se pare exagerat de mult.pls dc stiti o idee mai simpla da-ti un reply pls.
tx again  

[•silviug]

Pai ai memorie multa. E okay daca declari un vector de 1 milion de int-uri. Acum ca stii asta gandeste-te cum iti optimizezi solutia.

[•wickedman]

daca vrei sa folosesti functia totient si sa optimizezi timpul de executie te poti folosi de urmatoarele egalitati:

t(p^e) = (p - 1) * p^(e - 1), p numar prim (din definitie)
si
daca p numar prim, p NU divide a,
t(p^e * a) = t(p^e) * t(a) = (p - 1) * p^(e - 1) * t(a)

deci, daca la un moment dat stii t(1), t(2) ... t(n) poti calcula t(n + 1) gasind un singur divizor prim al lui n + 1

[•mcbrood]

okay, de data asta am pus algoritmul in practica si merge...numai ca la 7 din 10 teste imi depaseste timpul d exec. incerc sa optimizez formula si algoritmul in sine. oricum, a mers vectorul de 1 mil de char...amazing  ...
am citit si reply-ul tau wickedman...dupa ce am facut prima implementare si am scos si io formulele alea. m-am lovit insa de o noua problema. chiar vreau sa tin minte toate valorile obtinute in functiile totentiale precedente lui n+1 ? la fel, ma lovesc de probleme cu memoria si scrierea algoritmului. oricum as incerca sa fac sunt aproape convins ca nu pot sa scot 100 de puncte. voi ce alta abordare a problemei imi recomandati ?

[•silviug]

Bai nene.. nu-ti fie frica sa folosesti memorie.. este la greu .. 16 Mega cel putin. Lafaiala .. Declara vectori de care vrei cum vrei numai sa mearga mai bine. Ce a spus wickedman, daca implementezi direct, cu un vector de int-uri oricat de mare ti s-ar parea, intra in timp.

Asa ca treci la lucru

[•mcbrood]

am reusit intr-un final dar nu am mai folosit alea pt ca imi complicau mult treaba.pur si simplu calculam folosind ciurul lui eratostene si adaugam la numarul mare.am luat 100 de puncte.tx again pt sfaturi.