003 Fractii

[•catalaur]

am citit toate indiciile de pe forum, dar tot nu inteleg cum sta treaba cu ciurul lui eratostene...nu ma prind kum m`ar ajuta generarea numerelor prime pentru cazul in care eu trebuie sa verific dak a si b sunt prime intre ele

citeste despre functia totient in special. aia te ajuta 

Pai o fractie este ireductibila daca cel mai mare divizor comun este 1.

Revenind la problema, care e treaba cu testele , imi ia timp de executie > 2secunde , iar codul este destul de simplu.

[•astronomy]

Poate ca este simplu, dar nu este destul de performant. Citeste tot topicul la problema asta, sunt o gramada de sfaturi utile.

[•jupanu92]

Daca as face cu doua for-uri si dupaia sa calculez ptr i si j cel mai mare divizor comun ar intra in timp

[•Mishu91]

Daca as face cu doua for-uri si dupaia sa calculez ptr i si j cel mai mare divizor comun ar intra in timp

Nu. Iei km de 10 puncte asa.
Se rezolva cu functia lui euler... gasesti mai multe despre functia asta dak citesti toate paginile de pe forum despre problema

[•Mishu91]

http://infoarena.ro/forum/index.php?topic=2512.0
Acilea arata qm se calculeaza mai simplu phi(n) 

Offtopic: Cine ti-i diriga k vad k esti din bv, din liceu de info

[•BOgdu]

Am facut programul cu 2 "For" si am verificat daca sunt prime intre ele (adica daca cmmdc=1,prin scaderi repetate). Am pus in fractii.in toate exemplele de la pag1, inafara de 1000000 si imi da bine, dar la evaluare dc iau 0 ?
Borland Pascal--

[•gabitzish1]

Rezolvarea ta nu este una optima, de aia iei pe cateva teste Time limit exceeded. Pentru raspunsurile gresite nu stiu ce explicatie sa'ti dau daca zici ca iei toate testele.

[•fireatmyself]

raspunsul poate sa fie destul de mare si ar trebui sa folosesti tipul de date 'extended' (nu mai tin minte exact daca acesta iti retinea numerele pana in 2^64). downloadeza-ti free pascal, deoarece borlandul are multe restrictii (incepand cu memoria si terminand cu tipurile de date). citeste intai documentatia (in special la evaluator), apoi downloadeaza-ti compilatoarele folosite de infoarena si, in cele din urma, citeste acest forum si incearca sa gasesti o rezolvare care se incadreaza in timp.

Spor! 

[•BOgdu]

Eu acum sunt la info, si am intrebat`o si pe dira ..si am mai optimizat`o si am luat numa 10...cand ajung acasa, o fac in free pascal

[•devilkind]

in pascal ptr numere pana la 2^64 foloseste int64, bineinteles asta in freepascal, borlandul nu cred ca stie.
@Bogdu: Ti s-a zis si mai sus ca algoritmul tau nu este optim. Degeaba incerci sa optimizezi o sa iei maxim 30 de pct sa zicem, ca sa iei 100 trebuie sa schimbi algoritmul cam de pe la radacina.

[•andrici_cezar]

am o intrebare? cum arata ultimul test. Mie imi da doar 90 de puncte. Aveti vreo ideie cum pot inbunatati acest timp de 2048 de ms si cum sa imbunatatesc problema pana la 100 de puncte?

in pascal ptr numere pana la 2^64 foloseste int64, bineinteles asta in freepascal, borlandul nu cred ca stie.
@Bogdu: Ti s-a zis si mai sus ca algoritmul tau nu este optim. Degeaba incerci sa optimizezi o sa iei maxim 30 de pct sa zicem, ca sa iei 100 trebuie sa schimbi algoritmul cam de pe la radacina.

mie nu mia mers cu int64 dar iti merge cu qword, dar intr-un fel ai dreptate deoarece trebuie sa schimbi programul ca altfel iti iese aiurea timpul la ultimul test. Oricum pe mn ma poate ajuta cineva?

Editat de moderator: Nu posta consecutiv pe aceeasi tema! Modifica mesajele precedente!

[•criscer]

cum poate fi gasit cel mai mare divizor comun a doua numere in turbo pascal?
   mersi anticipat...

[•devilkind]

cu algoritmul lui euclid, poti gasi mai multe detalii in topicul destinat problemei 001. CMMDC

[•andrici_cezar]

Pe mine cine ma poate ajuta ca tot nu primesc raspuns? De ce ia atat de mult si cum as putea sa inbunatatesc timpul

[•b.ionut]

Salut,

Incerc si eu de cateva zeci de minute sa rezolv aceasta problema insa fara succes ( inca ). Am citit cam tot ce ati scris in acest topic .

Eu am ajuns pana la faza generarii tuturor fractiilor, mai exact :

 

Cod:

for (i=1;i<=n;i++)  
  {  
      for (k=1; k<=n; k++)  
      {  
         p = i;  
         q = k;    
         // cout<<"P/Q = "<<p<<" / "<<q<<endl;
      }  
  }  

Practic, ma intereseaza ca din aceste toate fractii sa le dau pe cele reductibile la o parte iar pe celelalte sa le adun intr-o variabila s pe care sa o salvez apoi in fractii.out .

Aveti un link unde as putea citi despre o solutie pentru situatia mea, please ?

Am observat ca link-ul de pe forum despre Ciurul lui Eratosthenes nu mai functioneaza .

Mersi,

[•Florian]

Daca ai citit intreg topicul, inseamna ca ai vazut faptul ca problema se rezolva utilizand functia totentiala. tot(n) este o functie care iti intoarce numarul de numere prime cu n si mai mici decat n. Din cauza faptului ca ai nevoie de toate tot(i) (cu i<=n), e mult mai bine sa precalculezi la inceput intr-un vector, valorile respective. Ca sa faci aceasta precalculare, te folosesti de Ciurul lui Eratostene .

Functia totentiala este : tot(n) = n*(1-1/p1)*(1-1/p2)...*(1-1/pk), unde p1,p2,...,pk sunt factorii primi care apar in descompunerea lui n.

In legatura cu solutia prezentata de tine, complexitatea ei e O(n^2), si avand in vedere ca n este 1 milion, cu siguranta nu o sa iti intre in timp, indiferent daca iti va da corect. Succes!

[•Necro]

Lamuritima putin, deci.... atunci cand e sus numar impar atunci jos apar si impare si pare, si atunci cand e sus numar par atunci jos apar numai impare, cu conditia ca sa nu fie egale cu numaru de sus.
Alta regula nu gasesc, spunetimi voi....e greu

Spunetimi va rog care e formula completa, ca nu potsa o deduc.Eu cred ca e in felu urmator
Atunci cand e sus numar impar, atunci apar fractii care au numitor si par si impar
Cand numaratoru e par, atunci la numitor sunt numai fractii impare , cu conditia ca sa nu fie egale cu numaratoru . Ma insel ?

[edit] nu mai posta de 2 ori consecutiv, foloseste butonul "modifica"

[•Florian]

Problema nu are nicio treaba cu paritatea numerelor. In schimb, are treaba cu numarul de numere relativ prime cu n si mai mici ca n(n - un nr dat). Citeste tot topicul asta, si sunt sigur ca vei gasi rezolvarea. Succes!

[•Necro]

atunci nici nu ma apuc de ea...e grea si neinteresanta...nici macar nu stiu cum e ciuru' lu erastotene si nici nu inteleg nimic daca ma uit pe net..treb sa imi expl cineva..sunt doar cls a 9-a :\ ffs

[•Florian]

e grea si neinteresanta.

Atunci zi-mi motivul pt care ai cerut lamuriri referitor la aceasta problema 'neinteresanta'. Sunt foarte curios.

[•sigrid]

nu stiu cum e ciuru' lu erastotene si nici nu inteleg nimic daca ma uit pe net..treb sa imi expl cineva..

Pentru ciur incearca sa te uiti in arhiva educationala aici : http://infoarena.ro/problema/ciur. Si ca sa intelegi mai bine pe sursele celor care au facut problema. Arhiva educationala este conceputa pentru incepatorii care vor sa invete lucruri noi.

Cat despre surse, inclusiv problema fractii are acces liber la sursele trimise. Daca e ceva ce nu intelegi, trimite-mi un mesaj personal si o sa-ti explic eu cum functioneaza ciurul.

[•Davide]

Este foarte simpla, insa exemplul este gresit, 1/1 nu este fractie ireductibila.

dACA bagati 4 si va da 8 e bine! 1/1, 2/1, 3/1 si 4/1 nu trebuie luate in calcul.

[editat de moderator] Nu mai posta consecutiv, foloseste butonul "Modifica".

[•DraStiK]

Este foarte simpla, insa exemplul este gresit, 1/1 nu este fractie ireductibila.

dACA bagati 4 si va da 8 e bine! 1/1, 2/1, 3/1 si 4/1 nu trebuie luate in calcul.

[editat de moderator] Nu mai posta consecutiv, foloseste butonul "Modifica".

daca citesti cu atentie cerinta ai sa vezi ca fiecare fractie de forma nr/1 e considerata ireductibila si de aceea 1/1, 2/1 samd trebuie luate in considerare

[•wefgef]

Sa citim putin definitia unei fractii ireductibile.

Sa aruncam o privire asupra fractiei 4/2 (a = 4, b = 2). Daca am considera ca 2/1 (consideram toate cele 4 posibilitati in functie de semne: -2/1, 2/-1, -2/-1, 2/1) nu este fractie ireductibila, atunci nu am putea gasi alte doua valori c si d cu proprietatea ca a/b = c/d, |c| < |a| si |d| < |b|. De aici ar rezulta ca 4/2 este o fractie ireductibila - evident, fals.

Putem trage concluzia ca 2/1 este o fractie ireductibila.

[•alexandru92]

imi explica si mie ce e gresit la rezolvarea asta:
in vectorul phi[ i ] -retin cate numere prime cu i is in sirul  1,2,....n.
Initial  vectorul are phi[1]=n si  restu  phi[ i ]=n-1,i>1;
Si aplic  ciurul lui eratostene , scazand din phi[ i ] si  phi[ i*j ] cate  1. Iar apoi rezultatul e suma lor.
Sursa implementata e aici.

[later] Am  gasit  eroarea