003 Fractii

[•Florian]

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 

[•yrar]

asa nu mai merge. nu scrie nimic in fisier, se si blocheaza sau dureaza mult timp executia ...

[•Florian]

Cu

Cod:

d = 2;
while(n>1)
  {
     if(n%d==0) 
       {  
          pr = pr - pr/d;
          while(n%d==0) n/=d;
       }
  d++;
  }

se blocheaza? 

[•yrar]

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 ...

[•Florian]

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:

Cod:

sol = 1;
for(i=2;i<=N;i++)
          sol += 2*phi[i];

[•yrar]

modificasem inainte programul si aveam niste erori, l-am facut iar si merge si scot 30 pct. acum incerc cu ciurul lui eratostene

[•matzipan]

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?

Cod:

#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;
}

[•wefgef]

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.

[•matzipan]

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.

[•yrar]

Cod:

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.

[•matzipan]

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.

[•wefgef]

http://infoarena.ro/forum/index.php?topic=2512.0 

[•matzipan]

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.

[•vladtarniceru]

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.
 

Cod:

 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

Cod:

#include<math.h>

mod(....);

Cod:

include<math.h>

in C/C++.in pascal nu mai stiu

[editat de moderator] nu mai posta consecutiv, foloseste butonul "modifica"

[•sima_cotizo]

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...

[•vladtarniceru]

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

[•sima_cotizo]

Exista deja pe forum un topic pe tema asta.

In plus, e a doua oara cand iti zic: chiar si topicul acesta are 10 pagini pline de idei. Ai incercat sa treci prin ele?

[•vladtarniceru]

am incercat,dar tot nu prea am inteles(sunt in clasa a6-a  ).Si pe sursa mea iau doar 10 puncte.

Cod:

#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:

[•Mishu91]

Algoritmul tau obtine 10 puncte pentru ca este ineficient. Citeste toate paginile acestui topic si cu siguranta vei gasi destule indicii necesare.

[•SpiderMan]

Nu stiu ce are, imi da raspuns gresit la cateva teste, imi spuneti de ce? Merci
http://infoarena.ro/job_detail/378202?action=view-source
GATA am depistat era nr care trebuia int64 merci.

[•C0Mr4d3]

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:

Cod:

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)...

[•SpiderMan]

Nu cred ca e "corecta" si "eficienta" rezolvarea, pentru ca tu oricum trebuie sa aflii fractiile ireductibile, deci faci in plus anumite chestii.

[•C0Mr4d3]

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...

[•Florian]

Fara demonstratie matematica, nu poti spune ca solutia e corecta. 

[•SpiderMan]

Poti sa scrii cum ai ajuns la acest lucru (poti sa-l demonstrezi cumva?), eventual da-mi niste exemple sa vad ..