•Florian
|
|
« Răspunde #225 : Septembrie 29, 2009, 20:24:53 » |
|
In loc de "pr=pr*((d-1)/d)" incearca " pr -= pr/d ". E acelasi lucru, doar ca am desfacut parantezele. Si sterge "else"-ul "d++"-ului din while, ca altfel va cicla la primul factor prim gasit. Scuze pt exprimare
|
|
|
Memorat
|
|
|
|
•yrar
Strain
Karma: -1
Deconectat
Mesaje: 17
|
|
« Răspunde #226 : Septembrie 29, 2009, 20:46:55 » |
|
asa nu mai merge. nu scrie nimic in fisier, se si blocheaza sau dureaza mult timp executia ...
|
|
|
Memorat
|
|
|
|
•Florian
|
|
« Răspunde #227 : Septembrie 29, 2009, 21:54:15 » |
|
Cu d = 2; while(n>1) { if(n%d==0) { pr = pr - pr/d; while(n%d==0) n/=d; } d++; }
se blocheaza?
|
|
|
Memorat
|
|
|
|
•yrar
Strain
Karma: -1
Deconectat
Mesaje: 17
|
|
« Răspunde #228 : Septembrie 30, 2009, 13:33:05 » |
|
ah, scuze. credeam ca fara ++d, acum am vazut ca l-ai pus in afara ifului. asa merge dar nu da pentru toate, merge pe 3,4 si inca, cateva mici, dar pe altele da prost. de ex pentru 31, imi da 647... ii ceva in neregula cu functia ? si la un milion imi iese din timp ...
|
|
« Ultima modificare: Septembrie 30, 2009, 13:40:49 de către Mardare Rares »
|
Memorat
|
|
|
|
•Florian
|
|
« Răspunde #229 : Septembrie 30, 2009, 14:56:06 » |
|
Ca sa intre in timp pt 1 milion, trebuie sa te folosesti de Ciurul lui Eratostene. Codul pare ok. Nu stiu exact unde gresesti. poti renunta la vectorul v[]. Eu am asa: sol = 1; for(i=2;i<=N;i++) sol += 2*phi[i];
|
|
|
Memorat
|
|
|
|
•yrar
Strain
Karma: -1
Deconectat
Mesaje: 17
|
|
« Răspunde #230 : Septembrie 30, 2009, 15:51:42 » |
|
modificasem inainte programul si aveam niste erori, l-am facut iar si merge si scot 30 pct. acum incerc cu ciurul lui eratostene
|
|
|
Memorat
|
|
|
|
•matzipan
Strain
Karma: -3
Deconectat
Mesaje: 10
|
|
« Răspunde #231 : Septembrie 30, 2009, 22:27:23 » |
|
Salut. Prima data am incercat o metoda foarte greoaie, si m-am uitat prin alte surse, recunosc, si am vazut ciurul, si m-am gandit sa-l optimizez. Algoritmul meu memorie foloseste clar mai putina, si timpii ar trebui in mod normal sa fie mai mici, dar e de 0 puncte. Pe exemplele alea cu 3,4,5 imi da bine, dar pe numere mai mari nu da bine (spre exemplu la 10 da 84 in loc de 64). Problema e ca daca x*i >= N, din nr-le ala nu se mai scade nimic, automat depaseste. Any ideas? #include <fstream> using namespace std; ifstream in("fractii.in"); ofstream out("fractii.out"); long N,i,x,nr; long eratostene() { long nr; nr=N; for(x=2; x*i<N; x++) nr--; return nr; } int main() { in>>N; nr=0; for(i=2;i<=N;i++) nr+=eratostene(); out<<nr; return 0; }
|
|
|
Memorat
|
|
|
|
•wefgef
|
|
« Răspunde #232 : Octombrie 01, 2009, 05:36:40 » |
|
De multe ori, in loc sa ii intrebi pe ceilalti "De ce nu merge?", ar trebui sa te intrebi pe tine insuti "De ce ar trebui sa mearga?". Daca nu ai inteles cum se rezolva problema, nu castigi nimic, chiar daca te uiti prin alte surse si reusesti sa iei 100 de puncte.
|
|
|
Memorat
|
omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
|
|
|
•matzipan
Strain
Karma: -3
Deconectat
Mesaje: 10
|
|
« Răspunde #233 : Octombrie 01, 2009, 11:18:07 » |
|
Hm... Doar ca idee, nu am intrebat de ce nu merge ci daca are cineva vreo idee. Am inteles cum se rezolva, dar solutia mea iesea rau din timp. Si m-am uitat la o singura sursa si am vazut eratostenele. Oricum nu l-am copiat, am facut un ciur al meu, care clar e mai potrivit problemei. Cred ca imi lipseste un if, sau am intervalele din for-uri prea mari.
P.s: nu prea ma descurc la genul asta de probleme, si vreau sa ma obisnuiesc cu ele, chiar nu trebuie sa te porti asa.
|
|
|
Memorat
|
|
|
|
•yrar
Strain
Karma: -1
Deconectat
Mesaje: 17
|
|
« Răspunde #234 : Octombrie 01, 2009, 18:23:34 » |
|
long N,i,x,nr; long eratostene() { long nr; nr=N; for(x=2; x*i<N; x++) nr--; return nr; }
si eu sunt la inceput, sper sa nu gresesc ce zic dar: ai declarat i global, si in for ai conditia x*i<N ... care ii mereu adevarata daca N>0 nu stiu cum iti iese pe numere mici. zic eu ca mai intai ar trebui sa inveti baza (notiuni elementare) si pe urma sa treci la probleme.
|
|
|
Memorat
|
|
|
|
•matzipan
Strain
Karma: -3
Deconectat
Mesaje: 10
|
|
« Răspunde #235 : Octombrie 02, 2009, 08:46:03 » |
|
Nu cred ca acolo e problema, pentru ca e ciurul lui eratostene pentru a afla numerele prime intre ele. Ideea e ca atunci cand 2*i>N, nu mai intra in for si imi aduna in plus. Am incercat cu un if(x*i>=N), ia sa incerc si cu un if(2*i>=N) nr=0; L.e: hmmmmmmm no. this shit need some thinkin nigga.
|
|
« Ultima modificare: Octombrie 02, 2009, 08:53:45 de către Zisu Andrei »
|
Memorat
|
|
|
|
•wefgef
|
|
« Răspunde #236 : Octombrie 02, 2009, 10:24:00 » |
|
|
|
|
Memorat
|
omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
|
|
|
•matzipan
Strain
Karma: -3
Deconectat
Mesaje: 10
|
|
« Răspunde #237 : Octombrie 02, 2009, 18:50:18 » |
|
Trebuie sa diger putin algoritmul, ca nu inteleg foarte bine de ce phi-=phi[j]; o sa ma uit pe un exemplu la el. Dea dumnezeu sanatate wefgef.
Inteleg ca scade atat i cat si primele cu i, dar nu cred ca am inteles eu prea bine.
|
|
« Ultima modificare: Octombrie 02, 2009, 19:24:40 de către Zisu Andrei »
|
Memorat
|
|
|
|
•vladtarniceru
|
|
« Răspunde #238 : Noiembrie 20, 2009, 17:57:18 » |
|
definitie:pentru ca o fractie sa fie ireductibila,(numarator,numitor)=1(cel mai mare divizor comun al numitorului si numaratorului trebuie sa fie 1),adica numaratorul si numitorul sa fie prome intre ele ,locu 1 dupa ce o fac(eti).parerea mea,faceti cu subprogram,dar nu gatantez ca o sa va dea 100 de puncte. int prim(long m,long h){ while(m!=h) if(m>h) m-=h; else if(m<h) h-=m; return h; } bafta am uitat sa spun asta e var recursiva incercati s-o imbunatatiti(ca timp de executie) cu modul in mod(....); in C/C++.in pascal nu mai stiu [editat de moderator] nu mai posta consecutiv, foloseste butonul "modifica"
|
|
« Ultima modificare: Noiembrie 21, 2009, 11:35:37 de către Sima Cotizo »
|
Memorat
|
|
|
|
•sima_cotizo
|
|
« Răspunde #239 : Noiembrie 21, 2009, 11:40:25 » |
|
Ce e recursiv in ce ai scris si la ce te ajuta? Cred ca mai bine citesti inainte prin topic idei de rezolvare si incerci sa bagi o sursa, problema nu e dintre cele usoare care pot fi trecute cu vederea...
|
|
|
Memorat
|
|
|
|
•vladtarniceru
|
|
« Răspunde #240 : Decembrie 10, 2009, 15:25:10 » |
|
problema asta e frumoasa,dar am alta idee.pt a vedea daca 2 nr sunt prome intre ele scadem din cel mai mare cel mai mic pana nr sunt egale (ex:12,8,12-8=4.ramane 4,8.8-4=4.ramane 4,4 =>(12,8)=4).asta e recursiva.dar mai e si altfel.de imparte cel mare la cel mic si se pastreaza restul,pana unul din resturi este 0.atunci afisam numarul nenul(ex:12,8,12%8=4.ramane 4,8.8%4=0.ramane 0,4 => (12,8)=4).poate o sa para absurd,dar e algoritmul lui euclid .si mai e ceva.ajutati-ma si pe mine,care e ideea cu ciurul lui eratostene?memoram toate nr si apoi verificam cu un for daca e sau nu prim? ca de exemplu numarele 4 si 21 nu sunt prime dar sunt prime intre ele
|
|
|
Memorat
|
|
|
|
|
•vladtarniceru
|
|
« Răspunde #242 : Decembrie 10, 2009, 16:09:14 » |
|
am incercat,dar tot nu prea am inteles(sunt in clasa a6-a ).Si pe sursa mea iau doar 10 puncte. #include<fstream.h> int prim(long n,long m){ while(m!=0 && n!=0) (m>n?m=m%n:n=n%m); if(n!=0) return n; return m; } ifstream f("fractii.in"); ofstream g("fractii.out"); int main(){ long t,n,m,nr=0; f>>t; nr+=t*2-1; for(n=2;n<=t;n++) for(m=2;m<=t;m++) nr+=(prim(n,m)==1); g<<nr; g.close(); return 0; }
asta e prog meu,poate isi da cineva seama....BAFTA:peacefingers:
|
|
|
Memorat
|
|
|
|
•Mishu91
|
|
« Răspunde #243 : Decembrie 10, 2009, 18:50:11 » |
|
Algoritmul tau obtine 10 puncte pentru ca este ineficient. Citeste toate paginile acestui topic si cu siguranta vei gasi destule indicii necesare.
|
|
|
Memorat
|
|
|
|
|
•C0Mr4d3
Strain
Karma: 1
Deconectat
Mesaje: 5
|
|
« Răspunde #245 : Ianuarie 30, 2010, 15:43:30 » |
|
M-am apucat sa rezolv problema si mi-e venit o idee...(nu stiu daca se poate rezolva asa) Am ajuns la concluzia ca nr fractii = n + suma_fractiilor_cu_numarator_par + suma_fractiilor_cu_numarator_impar ; unde: suma_fractiilor_cu_numarator_par = (n div 2) * (n - n div 2) suma_fractiilor_cu_numarator_impar = (n - n div 3) + (n - n div 5) + (n - n div 7)... + (n - n div i) i trecand prin toate numerele impare <= n Mai ramane doar sa scad exceptiile: 6/3 6/9 9/3 9/6 10/5 12/3 ... adica fractiile cu numitor impar si care se pot simplifica...dar aici m-am impotmolit Oare se poate duce la capat problema prin metoda asta? Asta e sursa din care nu am scazut exceptiile: program fractii; var f:text; n,i,s:1..1000000; begin assign(f,'fractii.in'); reset(f); readln(f,n); close(f); assign(f,'fractii.out'); i:=3; s:=n+(n div 2)*(n - n div 2); while i<=n do begin s:=s+(n-n div i); i:=i+2; end; rewrite(f); writeln(f,s); close(f); end.
Stiu ca nu functioneaza pe numere foarte mari...nu asta ma intereseaza ci daca se poate rezolva asa sau m-am chinuit degeaba (am umplut cateva pagini de formule)...
|
|
|
Memorat
|
|
|
|
•SpiderMan
|
|
« Răspunde #246 : Ianuarie 30, 2010, 16:56:00 » |
|
Nu cred ca e "corecta" si "eficienta" rezolvarea, pentru ca tu oricum trebuie sa aflii fractiile ireductibile, deci faci in plus anumite chestii.
|
|
|
Memorat
|
|
|
|
•C0Mr4d3
Strain
Karma: 1
Deconectat
Mesaje: 5
|
|
« Răspunde #247 : Ianuarie 31, 2010, 13:22:06 » |
|
defapt tot ce calculez in plus sunt acele exceptii de care ziceam, formulele pe care le-am gasit sunt pentru fractii ireductibile...deci daca cumva pot sa scad exceptiile, rezolvarea ar fi mai eficienta decat altele (am o singura structura repetitiva)... Problema este ca nu vad un tipar pentru exceptii, nu gasesc o formula...
|
|
|
Memorat
|
|
|
|
•Florian
|
|
« Răspunde #248 : Ianuarie 31, 2010, 13:28:53 » |
|
Fara demonstratie matematica, nu poti spune ca solutia e corecta.
|
|
|
Memorat
|
|
|
|
•SpiderMan
|
|
« Răspunde #249 : Ianuarie 31, 2010, 13:47:12 » |
|
Poti sa scrii cum ai ajuns la acest lucru (poti sa-l demonstrezi cumva?), eventual da-mi niste exemple sa vad ..
|
|
|
Memorat
|
|
|
|
|