Pagini: [1] 2 3   În jos
  Imprimă  
Ajutor Subiect: 010 Ciurul lui Eratosthenes  (Citit de 47979 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
filipb
Nu mai tace
*****

Karma: 232
Deconectat Deconectat

Mesaje: 929



Vezi Profilul
« : Februarie 27, 2008, 18:53:13 »

Aici puteti discuta despre problema Ciurul lui Eratosthenes.
Memorat
Prostu
Nu mai tace
*****

Karma: 134
Deconectat Deconectat

Mesaje: 323



Vezi Profilul
« Răspunde #1 : Martie 01, 2008, 11:14:28 »

Daca limita lui N era putin mai mica, pe undeva pe la 960000, problema asta se putea rezolva si pe Borland C++ 3.1.
In primul rand nu ai nevoie de numerele pare, pentru ca 2 este singurul numar par prim. Dupa aceea nu ai nevoie decat de un singur bit pentru a sti daca numarul curent este prim. Putea fi implementat deci folosind un singur vector unsigned char de 60000 folosindu-se desigur operatiile pe biti. Fiecarui numai impar i ii corespundea bitul i / 2 din vector, si fiecarui bit i din vector ii corespundea numarul 2 * i + 1. Daca imi aduc bine aminte, ciurul implementat astfel intra chiar si pe Borland in 0.5 secunde.
Memorat
sigrid
De-al casei
***

Karma: 61
Deconectat Deconectat

Mesaje: 129



Vezi Profilul
« Răspunde #2 : Martie 07, 2008, 20:39:29 »

Mi se pare putin, numai putin, exagerat faptul ca 8 din 10 teste pica daca in fisier se afiseaza mai mult de 1000 de numere.
Prioritatea acestei probleme ar trebui sa fie generarea ciurului, nu numarul de elemente puse in fisier.
Memorat
filipb
Nu mai tace
*****

Karma: 232
Deconectat Deconectat

Mesaje: 929



Vezi Profilul
« Răspunde #3 : Martie 07, 2008, 21:11:55 »

Fisierul de iesire contine 1000 de numere pentru a evita folosirea fisierelor de dimensiuni foarte mari. Primele 1000 de numere prime se ating pentru N aproximativ 10000, si pentru N 10000 merge o solutie si in O(NsqrtN), care nu ar trebui sa ia mai mult de 20-30 de puncte Smile.
Memorat
domino
Echipa infoarena
Nu mai tace
*****

Karma: 281
Deconectat Deconectat

Mesaje: 1.340



Vezi Profilul WWW
« Răspunde #4 : Martie 07, 2008, 21:18:20 »

Cred ca astfel de restrictii sunt chiar impotriva spiritului arhivei educationale. Nu cred ca ar fi fost o problema prea mare daca se afiseaza toate numerele prime sau eventual, se poate cere doar numarul lor.
Memorat
Cosmin
Echipa infoarena
Nu mai tace
*****

Karma: 351
Deconectat Deconectat

Mesaje: 1.799



Vezi Profilul
« Răspunde #5 : Martie 08, 2008, 01:06:43 »

Nici mie nu mi-a placut chestia cu 1000 de numere, era deajuns numarul de nr prime. Vroiam sa bag varianta de ciur optimizat pe biti, si dupa ce am vazut ca mai trebuie sa afisezi si altceva am lasat-o balta.
Memorat
bogdan2412
Echipa infoarena
Nu mai tace
*****

Karma: 410
Deconectat Deconectat

Mesaje: 951



Vezi Profilul
« Răspunde #6 : Martie 08, 2008, 08:52:01 »

Ajungeti sa considerati afisarea cea mai grea parte din problema ... Sa afisezi numerele nu ia mai mult de 3 linii...

Oricum daca se modifica enuntul acum tb reevaluate 23 de pagini de surse dintre care toti cei care au luat 100 pana acum o sa ia 20...
« Ultima modificare: Martie 08, 2008, 08:57:06 de către Bogdan Tataroiu » Memorat
Protoman
Infoarena Monthly
De-al casei
*****

Karma: 119
Deconectat Deconectat

Mesaje: 128



Vezi Profilul
« Răspunde #7 : Martie 08, 2008, 09:46:16 »

Ati putea cere sa se afiseze minim 1000 Think
Memorat
devilkind
Echipa infoarena
Nu mai tace
*****

Karma: 284
Deconectat Deconectat

Mesaje: 1.240



Vezi Profilul
« Răspunde #8 : Martie 08, 2008, 15:20:59 »

daca s-ar cere numai cate sunt prime, atunci sursele de 100 ar putea lua 100 in continuare. Wink
Memorat
filipb
Nu mai tace
*****

Karma: 232
Deconectat Deconectat

Mesaje: 929



Vezi Profilul
« Răspunde #9 : Martie 10, 2008, 13:40:13 »

La aceasta problema s-a modificat enuntul si s-au schimbat testele. In consecinta a fost facuta o reevaluare. Ne cerem scuze pentru eventualele neplaceri.
Memorat
vlad_oltean
Strain
*

Karma: 2
Deconectat Deconectat

Mesaje: 25



Vezi Profilul
« Răspunde #10 : Martie 12, 2008, 11:03:40 »

La aceasta problema s-a modificat enuntul si s-au schimbat testele. In consecinta a fost facuta o reevaluare. Ne cerem scuze pentru eventualele neplaceri.

acum m-am prins si eu... nu pricepeam de ce am 0p Rolling on the Floor Laughing
Memorat
zalman
Strain
*

Karma: -11
Deconectat Deconectat

Mesaje: 31



Vezi Profilul
« Răspunde #11 : Martie 30, 2008, 17:51:24 »

pls need help! am incercat sa o fac ...si pe testele mele imi merge bine...imi da o eroarea la compilare din cauza batranului borland 3.1 (array size to large) insa cand am trimis sursa am modificat marimea vectorului la 2000004 (char) si tot imi da ceva eroarea.habar nu am despre ce e vorba

"eroare de compilare in evaluator: In file included from /usr/include/c++/4.2/backward/fstream.h:31, from user.cpp:1: /usr/include/c++/4.2/backward/backward_warning.h:32:2: warning: #warning This file includes at least one deprecated or antiquated header. Please consider using one of the 32 headers found in section 17.4.1.2 of the C++ standard. Examples include substituting the <X> header for the <X.h> header for C++ includes, or <iostream> instead of the deprecated header <iostream.h>. To disable this warning use -Wno-deprecated. user.cpp: In function 'int main()': user.cpp:12: error: name lookup of 'i' changed for new ISO 'for' scoping user.cpp:10: error: using obsolete binding at 'i'"

 Brick wall
Memorat
sima_cotizo
Nu mai tace
*****

Karma: 219
Deconectat Deconectat

Mesaje: 596



Vezi Profilul
« Răspunde #12 : Martie 30, 2008, 18:03:23 »

Cod:
for (int i=2;i<=n;++i)   
    ciur[i]=1;   
 
for (i=2;i<=n;++i)

Aici e problema ta. In al doilea for nu mai stie cine e i-ul pe care mai sus l-ai declarat local. Asta merge in "batranul Borland", dar nu si in gcc. Pune i-ul la globale sau local in main si va merge!
Memorat
tm_radu
De-al casei
***

Karma: 16
Deconectat Deconectat

Mesaje: 140



Vezi Profilul
« Răspunde #13 : Martie 30, 2008, 18:03:49 »

Incearca sa inlocuiesti
Cod:
#include <fstream.h>

cu
Cod:
#include <fstream>
using namespace std;
Memorat

Daca nu merge o preblema, depaneaz-o, si abia apoi arunci calculatoru pe geam
Mishu91
Nu mai tace
*****

Karma: 169
Deconectat Deconectat

Mesaje: 751



Vezi Profilul
« Răspunde #14 : Mai 04, 2008, 12:15:01 »

O alternativa pentru ciurul pe biti(de departe cea mai buna modalitate, atat ca timp, cat si ca memorie), ar fi folosirea in loc de vectori de tip char vectorii de tip bool din STL. Avantaju este ca fiecare element este memorat pe un singur bit, si astfel se reduce mult memoria si timpul(aproape ca la ciurul pe biti... aici este evaluarea http://infoarena.ro/job_detail/187508), iar implementarea este aproape identica implementarii clasice.

L.E.: Cu ceva optimizari se poate ajunge la aceleasi performante de timp si memorie cu metoda pe biti http://infoarena.ro/job_detail/187607
« Ultima modificare: Mai 04, 2008, 18:27:24 de către Andrei Misarca » Memorat
wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« Răspunde #15 : Mai 04, 2008, 19:56:23 »

Incearca si cu bitset din STL - sunt curios cum merge. Vector de bool este dubios si se pare ca nu are mare viitor: http://en.wikipedia.org/wiki/Boolean_datatype#C.2B.2B. Oricum, deocamdata se pare ca face treaba Very Happy
Memorat

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
Mishu91
Nu mai tace
*****

Karma: 169
Deconectat Deconectat

Mesaje: 751



Vezi Profilul
« Răspunde #16 : Mai 04, 2008, 20:11:45 »

Ca uns merge Very Happy Super tare... scoate timpi kiar mai buni decat cu vector <bool> http://infoarena.ro/job_detail/187628
Memorat
Vlad_fisca
Strain


Karma: 1
Deconectat Deconectat

Mesaje: 6



Vezi Profilul
« Răspunde #17 : Noiembrie 13, 2008, 20:32:38 »

 Cam in cat timp imi afiseaza cu ciurul numerele prime din intervalul [1..64 000],folosind Ciurul lui Eratostene?
Memorat
devilkind
Echipa infoarena
Nu mai tace
*****

Karma: 284
Deconectat Deconectat

Mesaje: 1.240



Vezi Profilul
« Răspunde #18 : Noiembrie 13, 2008, 20:43:21 »

mai putin 0.1 secunde, ciurul lui erathostene daca e facut cum trebuie e foarte rapid, are complexitate O(N*ln N) daca nu ma inseala cunostintele de matematica.
Memorat
Vlad_fisca
Strain


Karma: 1
Deconectat Deconectat

Mesaje: 6



Vezi Profilul
« Răspunde #19 : Noiembrie 13, 2008, 20:52:30 »

 Mersi,Savin
 Se pot obtine mai mult de 30 de puncte pe algoritmul brut?sau e nevoie de optimizari?
Memorat
devilkind
Echipa infoarena
Nu mai tace
*****

Karma: 284
Deconectat Deconectat

Mesaje: 1.240



Vezi Profilul
« Răspunde #20 : Noiembrie 13, 2008, 21:22:44 »

nush exact ce intelegi prin algoritmul brut.
Uite aici un articol despre cum poti sa afli numerele prime folosind ciurul lui eratostene
Memorat
Florian
Nu mai tace
*****

Karma: 125
Deconectat Deconectat

Mesaje: 832



Vezi Profilul
« Răspunde #21 : Noiembrie 13, 2008, 21:24:36 »

Si in plus, ai acces la sursele celorlalti. Asadar, iti va fi mai usor sa inveti cum se face ciurul. Succes!   Thumb up
Memorat
Cosmin
Echipa infoarena
Nu mai tace
*****

Karma: 351
Deconectat Deconectat

Mesaje: 1.799



Vezi Profilul
« Răspunde #22 : Noiembrie 15, 2008, 00:49:45 »

@Tiberiu Dupa cum ziceam aici http://infoarena.ro/blog/intrebare-scurta ciurul are complexitate O(n log log n)
Memorat
k_ounu_eddy
Vorbaret
****

Karma: -104
Deconectat Deconectat

Mesaje: 161



Vezi Profilul
« Răspunde #23 : Decembrie 14, 2008, 14:36:26 »

Am o intrebare.Am citit si articolul cu ciurul lui Erathostenes,m-am uitat putin si pe codul cu optimizari pe biti,si am vazut ca foloseati peste tot tipul char.Asta complica mult lucrurile zic eu,nu ar fi mai simplu sa folosim tipul bool? Bineinteles,la OJI,ONI etc ii folositor acest lucru,ca nu ai bool acolo,dar aici unde se foloseste gcc e mai simplu,nu?
Memorat
wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« Răspunde #24 : Decembrie 14, 2008, 14:45:37 »

Un bool ocupa 8 biti (cel putin in C/C++, nu stiu in Java) si iti permita sa stochezi o singura valoare. Daca folosesti char atunci poti stoca pe 8 biti 8 valori, optimizand la maxim memoria folosita.

P.S.: La ONI se compileaza sub linux, in gcc Tongue.
Memorat

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
Pagini: [1] 2 3   În sus
  Imprimă  
 
Schimbă forumul:  

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