000 Algoritmul lui Euclid

[•wefgef]

Aici puteti discuta despre problema Algoritmul lui Euclid.

[•wefgef]

Din pacate ia 100 de puncte si o solutie in O(sqrt(A)).

[•DITzoneC]

Cel mai bine era sa se dea mai multe teste in fisier. (ca la euclid3)

[•filipb]

Datorita ineficientei testelor, la aceasta problema s-au schimbat atat enuntul, cat si testele folosite pentru evaluare. In consecinta, s-a facut o reevaluare a tuturor surselor trimise pana in prezent. Ne cerem scuze pentru eventualele neplaceri.

[•BigMazilu]

Ceva fooarte ciudat...  cum se face ca sursa asta :

#include <stdio.h>   
 
int T, A, B;   
 
int gcd(int a, int b)   
{   
    if (!b) return a;   
    return gcd(b, a % b);   
}   
 
int main(void)   
{   
    freopen("euclid2.in", "r", stdin);   
    freopen("euclid2.out", "w", stdout);   
 
    scanf("%d", &T);   
    for (; T; --T)   
    {   
        scanf("%d %d", &A, &B);   
        printf("%d\n", gcd(A, B));   
    }           
 
    return 0;   
} 

     - care este a lui Buruiana Filip, ia 100 de puncte, pe cand sursa mea-->

#include<iostream.h>   
#include<fstream.h>   
 
int t,a,b;   
 
  int cmmdc(int a, int b)   
  {   
       if(!b) return a;   
       return cmmdc(b,a%b);   
  }   
 
 
  int main()   
 {   
  ifstream f("euclid2.in");   
  ofstream g("euclid2.out");   
 f>>t;   
 for(t;t;--t)   
  {f>>a>>b;   
  g<<cmmdc(a,b)<<endl;   
  }   
  return (0);   
  } 

- care este absolut identic cu a lui Buruiana, ia numai 40 de puncte, dandu-mi TLE pe ultimele teste

[•wefgef]

Am facut si eu o sursa cu streamuri, am luat tot 40 . Nu e vina ta, se pare ca merg stremurile prea prost.

[•Prostu]

Din contra, streamurile merg mai repede. Lui victor ii ia foarte mult afisarea pentru ca foloseste 'endl'. Acesta din urma goleste bufferul dupa fiecare numar afisat. In locul lui ar trebui folosit '\n'. Lui wefgef cred ca ii merge incet pentru ca foloseste obiectele 'cin' si 'cout', care probabil nu sunt optimizate pentru citirea si respectiv scrierea in fisiere (posibil sa aibe un buffer mai mic sau deloc).

[•wefgef]

Mersi Prostule . O sa incerc din nou, sa vad cum merge.

[•rEbyTer]

La nationala pot folosi streamuri (in sensul efectivităţii).. adică ce e mai rapid .. un freopen sau un stream ?

[•fireatmyself]

poti sa folosesti. teoretic merge mai repede cu streamuri.

Din contra, streamurile merg mai repede. Lui victor ii ia foarte mult afisarea pentru ca foloseste 'endl'. Acesta din urma goleste bufferul dupa fiecare numar afisat. In locul lui ar trebui folosit '\n'. Lui wefgef cred ca ii merge incet pentru ca foloseste obiectele 'cin' si 'cout', care probabil nu sunt optimizate pentru citirea si respectiv scrierea in fisiere (posibil sa aibe un buffer mai mic sau deloc).

uite-te peste sursele de care vorbeste Filip ca sa te lamuresti

[•rEbyTer]

Păi, ca să mă asigur ,am făcut aceiaşi problemă atât cu streamuri , cât şi cu citirea standard din C.

cu streamuri
fără streamuri

Observ că la citirea standard este folosită mult mai puţina memorie.. (diferenţă de peste 100KB faţă de citirea cu streamuri) , ar trebui să mă îngrijoreze asta la unul dintre subiectele de la naţională?


L.E.: îmi place citirea standard din C , la faza:

Cod:

char c;
while(scanf("%c",&c)!=EOF)
   { fă-ţi treaba }

[•tvlad]

La nationala pot folosi streamuri (in sensul efectivităţii).. adică ce e mai rapid .. un freopen sau un stream ?

In sensul efectivitatii streamurile sunt mai dubioase, compilatorul le aduce dintr-un univers paralel si asta dureaza mult timp.
Ai aici un experiment legat de efectivitate, in caz ca vrei sa studiezi mai indeaproape subiectul.

PS: Pe versiuni de gcc mai vechi parca mergeau mai incet streamurile, nu?

[•rEbyTer]

PS: Pe versiuni de gcc mai vechi parca mergeau mai incet streamurile, nu?

Da.

Este prea efectiv sa folosesc cuvantul "efectiv" . Vroiam să spun eficient . Dar doar vroiam .

[•SpiderMan]

Imi explica si mie de ce la problema alg. lui euclid, la comentarii este link catre alg. lui euclid extins ? Merci.
[LE] Vad ca s-a rezolvat. Good job  

[•BigDaddyD]

Pentru a imbunatati timpul de rulare putem folosi algoritmul lui Euclid prin scaderi, ceea ce duce la obtinerea a 60 de puncte

cum se face ca am luat 100 cu euclid?
nu ca m-ar deranja

[•pauldb]

Pentru ca ai implementat prin impartiri. Citeste si tu ce citezi si apoi posteaza.

[•RaduDo2]

nu inteleg de ce iau punctaj atat de mic ... nu pot sa pricep ... am modificat sursa de cateva ori dar degeaba imi puteti da o indicatie? ma puteti ajuta va rog?

Cod:

#include<iostream.h>
#include<fstream.h>
int t,i,a,r,b;
int main()
{
	fstream f("euclid2.in",ios::in);
	fstream g("euclid2.out",ios::out);
f>>t;
if(t<=100000&&t>=1)
for(i=1;i<=t;i++)
{
	f>>a>>b;
	while(b!=0){
		r=a%b;
		a=b;
		b=r;}
	g<<a<<endl;
}
f.close();g.close();
return 0;
}

Editat de admin: Foloseste tagul "code" cand postezi surse.

[•klamathix]

De la endl ti se trage. Inlocuieste-l cu "\n".

[•Cosmin1490]

Eu zic asa:
-Schimba <fstream.h> in <fstream> si scrie dupa using namespace std;.
-Declara variabilele tale ca fiind locale si nu globale.

[•toni2007]

Eu zic asa:
-Schimba <fstream.h> in <fstream> si scrie dupa using namespace std;.
-Declara variabilele tale ca fiind locale si nu globale.

N-are nicio legatura ca a inclus "fstream.h" in loc de "fstream", pe infoarena e gcc 4.2. Abia din 4.3 e "fstream.h" deprecated. Iar legat de variabile, crede-ma ca n-are nicio importanta daca sunt locale sau globale, la cate are. Compilatorul isi face oricum niste optimizari.

Problema e de la endl. Endl goleste buffer-ul de scriere de fiecare data, pe cand afisarea "\n" nu. E ca si cum ai face fflush de fiecare data.

[•DevilShadow]

Imi poate zice si mie ce ii gresit la codul asta?

int cmmdc(int a, int b)
{
   if(!b) return a;
   return cmmdc(b, a % b);
}

Iar apelul e aici.
   f >> n;
   for(i = 0; i < n; i ++)
   {
      f >> a >> b;
      g << cmmdc(a, b) << endl;
   }
Imi da doar 30 de pc... si zice ca am depasit timpul. De ce?

[•andunhill]

Incearca sa inlocuiesti endl cu '\n'. Citeste mai sus de ce nu e indicat endl.

[•Petrean_Vlad]

E prea smecher tipul asta

[•tibi2012]

Imi ziceti si mie cum as putea optimiza programul cami da TLE pe ultimele 2 teste.

Cod:

var f,g:text;
    a,b,t,i:longint;
    v1,v2:array[1..1000] of longint;
begin
  assign(f,'euclid2.in');
  assign(g,'euclid2.out');
  settextbuf(f,v1);
  settextbuf(g,v2);
  reset(f);
  rewrite(g);
  readln(f,t);
  for i:=1 to t do
    begin
      readln(f,a,b);
      while a<>b do
        if a>b then
          dec(a,b)
        else
          dec(b,a);
      writeln(g,a);
    end;
  close(f);
  close(g);
end.

[•PlayLikeNeverB4]

In pagina problemei zice clar ca metoda cu scaderi nu intra in timp.