infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva educationala => Subiect creat de: Andrei Grigorean din Februarie 26, 2008, 11:10:24



Titlul: 002 Algoritmul lui Euclid extins
Scris de: Andrei Grigorean din Februarie 26, 2008, 11:10:24
Aici puteti discuta despre problema Algoritmul lui Euclid extins (http://infoarena.ro/problema/euclid3).


Titlul: Răspuns: 002 Algoritmul lui Euclid extins
Scris de: Silaghi Raul din Martie 04, 2008, 16:10:58
imi poate si mie spune care e diferanta dintre cele 2 coduri , job #148569 si job #148571 , pe al meu iau 10 puncte iar pe cel "imprumutat" :? 100 . de ce ?? :-s


Titlul: Răspuns: 002 Algoritmul lui Euclid extins
Scris de: Airinei Adrian din Martie 04, 2008, 16:21:36
In prima sursa ai cmmdc(n,m%n) in loc de cmmdc(m,m%n). Pe viitor te rog verifica putin sursa inainte sa postezi. De asemenea, asigura-te ca postezi acolo unde trebuie, tu ai trimis sursa la Algoritmul lui Euclid, nu euclid extins.


Titlul: Răspuns: 002 Algoritmul lui Euclid extins
Scris de: speedzeal din Aprilie 16, 2008, 16:59:41
Cu ce ar mai trebui sa optimizez ka sa imi dea 100?... ](*,)..
http://infoarena.ro/job_detail/180132


Titlul: Răspuns: 002 Algoritmul lui Euclid extins
Scris de: Tofan Vasile din Aprilie 16, 2008, 17:05:04
citirea si scrierea in C.
Ai fi vazut asta daca te-ai fi uitat pe celalalte surse.  :P


Titlul: Răspuns: 002 Algoritmul lui Euclid extins
Scris de: Bogdan-Alexandru Stoica din Aprilie 16, 2008, 17:41:52
@vasile: s-a luat 100 si cu citire in C++: http://infoarena.ro/job_detail/155936?action=view-source
@alex: in loc sa folosesti endl, foloseste '\n'. merge mai repede asa, deoarece endl goleste bufferul dupa fiecare numar afisat. http://infoarena.ro/job_detail/180182?action=view-source 


Titlul: Răspuns: 002 Algoritmul lui Euclid extins
Scris de: Cosmin Negruseri din Aprilie 17, 2008, 05:00:03
@bogdan in sfarsit carma pozitiva  :thumbup:


Titlul: Răspuns: 002 Algoritmul lui Euclid extins
Scris de: speedzeal din Aprilie 17, 2008, 09:27:05
@vasile: s-a luat 100 si cu citire in C++: http://infoarena.ro/job_detail/155936?action=view-source
@alex: in loc sa folosesti endl, foloseste '\n'. merge mai repede asa, deoarece endl goleste bufferul dupa fiecare numar afisat. http://infoarena.ro/job_detail/180182?action=view-source 
Mersi mult...a mers... :ok:


Titlul: Răspuns: 002 Algoritmul lui Euclid extins
Scris de: Sima Cotizo din Noiembrie 02, 2008, 08:09:51
Am mutat discutia despre factorizarea numerelor in alt topic:

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


Titlul: Răspuns: 002 Algoritmul lui Euclid extins
Scris de: Iacob Eduard din Decembrie 18, 2008, 18:59:52
As avea o intrebare despre articolul cu Algoritmul lui Euclid.Zice asa:
Citat
Cum a si b sunt divizibile cu d, atunci orice combinatie liniara a lor este divizibila cu d, inclusiv a - b * c = a%b.
Ce inseamna combinatie liniara?E acea combinatie de variabile,in care raportul lor e constant,nu?
De ex, avem 2 variabile a,b.Daca a/b=const => a si b sunt o combinatie liniara,nu?
Presupunand ca am dreptate,in articol zice inclusiv a-b*c=a%b. a%b e prima variabila.Si a doua care e atunci?Doar insusi cuvantul "combinatie" presupune "mai multe".
Sau poate vrea sa spuna "este divizibila cu d,inclusiv cu a-b*c=a%b".Explicati putin ce vrea sa spuna articolul aici.


Titlul: Răspuns: 002 Algoritmul lui Euclid extins
Scris de: Savin Tiberiu din Decembrie 18, 2008, 19:10:28
faptul ca orice combinatie a numerelor a,b divide un numar c, inseamna ca oricum am alege 2 numere x si y atunci a*x + b*y va divide numarul c. Cel putin asta inteleg eu prin combinatie liniara, ii asociezi fiecarui numar un coeficient si le aduni.
De exemplu o combinatie ptr sirul de numere a1, a2 ... an poate fi:
x1*a1 + x2*a2 .. + xn*an
unde sirul x1, x2 ... xn il alegi tu.

Sper ca nu zic prostii.


Titlul: Răspuns: 002 Algoritmul lui Euclid extins
Scris de: Iacob Eduard din Decembrie 19, 2008, 18:56:54
Ok,am consultat alte surse si cred ca ai dreptate.
Dar tot nu am inteles ce vrea sa spuna articolul.In enunt se precizeaza:

a,b - divizible cu d =>orice combinatie liniara divizibila cu d
limbaj matematic : a*x+b*y divizibil cu d (evident)

inclusiv a%b
limbaj matematic: (a%b)*x + ...
care e al doilea termen aici?
Si chiar daca am avea al doilea termen(m-am gandit ca poate ar fi b),ce legatura are combinatia asta liniara cu cmmdc.Adica ,ce trebuie sa demonstram, e faptul ca a si b au acelasi cmmdc cu b si a%b.De ce din combinatia aia liniara rezulta ca au acelasi cmmdc cele doua perechi de numere.
PS:sper ca ati inteles ce am spus




Titlul: Răspuns: 002 Algoritmul lui Euclid extins
Scris de: Andrei Grigorean din Decembrie 19, 2008, 19:23:30
Probabil ca daca ai folosi regulile de punctuatie si te-ai exprima coerent s-ar intelege mai bine ce vrei sa spui.


Titlul: Răspuns: 002 Algoritmul lui Euclid extins
Scris de: Savin Tiberiu din Decembrie 19, 2008, 19:52:44
Din faptul ca orice combinatie liniara a lui a si b divide pe d rezulta ca si a%b este divizibil cu d. De ce? pentru ca a%b poate fi scris ca o combinatie liniara a lui a si b.


Titlul: Răspuns: 002 Algoritmul lui Euclid extins
Scris de: Iacob Eduard din Decembrie 19, 2008, 19:58:39
Citat
Probabil ca daca ai folosi regulile de punctuatie si te-ai exprima coerent s-ar intelege mai bine ce vrei sa spui.
Eu cred ca folosesc destule semne de punctuatie.
La fel si cu coerenta.Sunt unii useri la care stau o gramada de timp sa inteleg ce au spus(din punct de vedere al coerentei).Sa nu mai spun ca multe articole sunt editate prost(greseli de exprimare,gramaticale etc).Asta e si motivul principal pt care pun acum intrebarile acestea pe forum.
[EDIT]:Am uitat sa ii multumesc lui Tiberiu.Am inteles cum stau lucrurile.


Titlul: Răspuns: 002 Algoritmul lui Euclid extins
Scris de: Andrei Grigorean din Decembrie 19, 2008, 19:59:32
Din faptul ca orice combinatie liniara a lui a si b divide pe d rezulta ca si a%b divide pe d. De ce? pentru ca a%b poate fi scris ca o combinatie liniara a lui a si b.

Probabil vrei sa spui ca orice combinatie liniara este divizibila cu d :P


Titlul: Răspuns: 002 Algoritmul lui Euclid extins
Scris de: Savin Tiberiu din Decembrie 19, 2008, 21:06:51
Intr-adevar, scuze :D


Titlul: Răspuns: 002 Algoritmul lui Euclid extins
Scris de: Cosmin Negruseri din Decembrie 20, 2008, 09:41:51
@Iacob, o chestie care imi sare in ochi de fiecare data cand citesc posturile tale e faptul ca nu lasi spatii intre punct si inceputul propozitiei noi, sau dupa o virgula, sau inainte de o paranteza. Asta face sa ma gandesc ca nu e scris ca lumea in loc sa ma concentrez la ce vrei sa zici. Am zis asta ca sa nu ai impresia ca doar Andrei are ceva cu posturile tale.


Titlul: Răspuns: 002 Algoritmul lui Euclid extins
Scris de: Iacob Eduard din Decembrie 20, 2008, 13:07:46
OK, am sa incerc de acum incolo.


Titlul: Răspuns: 002 Algoritmul lui Euclid extins
Scris de: Andrei Grigorean din Decembrie 20, 2008, 16:58:08
OK,am sa incerc de acum incolo

Amuzant, dupa virgula nu ai lasat spatiu mai sus :P


Titlul: Răspuns: 002 Algoritmul lui Euclid extins
Scris de: Iacob Eduard din Decembrie 22, 2008, 14:23:52
Am corectat.
Insa am zis ca o sa incerc, deci incercarea are si o rata de esec. Oricum imi asum greseala  :P
Ce nu inteleg eu, e cum o sa ajute aceste spatii, sa intelegeti mai bine post-urile mele. Nevermind  :)


Titlul: Răspuns: 002 Algoritmul lui Euclid extins
Scris de: Andrei Grigorean din Decembrie 22, 2008, 15:19:12
Daca lasi spatii dupa semnele de punctuatie (cum de altfel este corect sa scrii) creste lizibilitatea postului.


Titlul: Răspuns: 002 Algoritmul lui Euclid extins
Scris de: irimias robert din Ianuarie 29, 2009, 13:43:18
scz de inrtebare k ii cam offtopic, dar imi explica shi mie cnv de ce atunci cand pun << endl fata de  <<"\n" un test imi tine cu 150-200 ms mai mult ????    :-k


Titlul: Răspuns: 002 Algoritmul lui Euclid extins
Scris de: Pripoae Teodor Anton din Ianuarie 29, 2009, 13:45:31
S-a mai discutat pe forum despre asta. endl goleste bufferul de fiecare data dupa ce scrie, de aceea ia mult mai mult.


Titlul: Răspuns: 002 Algoritmul lui Euclid extins
Scris de: Margarit Ioan din Februarie 18, 2009, 00:46:25
La ultimul test imi iese din timp si ce ma pune pe ganduri e diferenta dintre timpi :-k
imi poate sugera cineva cum pot optimiza programul ca sa se incadreze? :fool:
http://infoarena.ro/job_detail/261158


Titlul: Răspuns: 002 Algoritmul lui Euclid extins
Scris de: Pripoae Teodor Anton din Februarie 18, 2009, 16:32:39
Cred ca e de la citire :P. Citeste direct cu readln. Eu cand am rezolvat asta am facut citirea in felul urmator:

Cod:
 
begin 
     assign(stdin,'euclid2.in');reset(stdin); 
     assign(stdout,'euclid2.out');rewrite(stdout); 
     readln(stdin,t); 
     for i:=1 to t do begin 
         readln(stdin,a,b); 
         writeln(stdout,cmmdc(a,b)); 
     end; 
     close(stdin); 
     close(stdout); 
end. 


Titlul: Răspuns: 002 Algoritmul lui Euclid extins
Scris de: Cezar Mocan din Februarie 19, 2009, 14:02:51
Eu stiam ca e in loc de stdin si stdout in Pascal sunt input si output :). Si nu e nevoie sa scrii
Cod:
readln(input, a);
E de ajuns
Cod:
readln(a);


Titlul: Răspuns: 002 Algoritmul lui Euclid extins
Scris de: Pripoae Teodor Anton din Februarie 19, 2009, 17:32:05
Da stiu :P. Doar ca atunci cand am rezolvat problema nu stiam smenul asta. Oricum nu cred ca este mai rapid asa. Cum am facut eu specifici explicit streamul de intrare, deci e posibil sa mearga mai rapid. E cam aceeasi chestie ca si cu scanf / printf vs fscanf / fprintf.


Titlul: Răspuns: 002 Algoritmul lui Euclid extins
Scris de: Codrea Marcel din Februarie 25, 2009, 23:24:48
Cred ca ar fi util daca ar exista si un link catre o solutie iterativa in pagina problemei.

Uite una :
http://infoarena.ro/job_detail/266684?action=view-source


Titlul: Răspuns: 002 Algoritmul lui Euclid extins
Scris de: UPB-Hulea-Ionescu-Roman din Martie 07, 2009, 18:27:19
ce este gresit la sursa asta? nu imi dau seama deloc  ](*,)
http://infoarena.ro/job_detail/272718

*am gasit greseala, functia cmmdc utiliza valori integer, le-am schimbat in longint si am luat 100 pct :)


Titlul: Răspuns: 002 Algoritmul lui Euclid extins
Scris de: Davide din Martie 11, 2009, 18:33:12
Unii oameni nu stiu sa faca nimic simplu? Programul meu nu foloseste algorimtul asta, si, chiar mai mult, returneaza mai mult de o valoare.
Cod:
program euclidextins;

var a,b,c,x,y,i,t:integer;

begin
     readln (a);
     readln (b);
     readln (c);
     {read}

     for x:=-c to c do
         for y:=-c to c do
             if (a*x+b*y=c) then writeln (a,'*',x,'+',b,'* ',y,'=',c);
     readln;
end.

[editat] Chiar daca se vede frumos si cum ai facut tu, data viitoare foloseste tag-ul "code"


Titlul: Răspuns: 002 Algoritmul lui Euclid extins
Scris de: Bogdan-Cristian Tataroiu din Martie 11, 2009, 20:51:05
Programul tau nu o sa intre in timp pentru date de intrare mari. Trimite sursa si vezi cate puncte iei. Dupa cum scrie si in explicatie, se poate extinde programul care foloseste algoritmul lui euclid sa returneze mai multe valori (sunt o infinitate de solutii :P ).


Titlul: Răspuns: 002 Algoritmul lui Euclid extins
Scris de: Birsan Dragos din Martie 20, 2009, 15:33:01
ba s-a stricat monitoru de evaluare sau de ce arata in continuu in asteptare? ](*,) nu mai are nici un farmec infoare daca nu verifica problemle :(


Titlul: Răspuns: 002 Algoritmul lui Euclid extins
Scris de: Moldovan Marcel din Martie 27, 2009, 10:03:47
prima mea pb rezolvata... am primit 100 pcte dar am creat acasa un fisier cu 100000 de numere si programul a terminat executia in 0.6 secunde pt datele din acest fisier (am cronometrat). deci depaseste timpul de executie din pb si totusi... am primit punctaj maxim


Titlul: Răspuns: 002 Algoritmul lui Euclid extins
Scris de: Florian Marcu din Martie 27, 2009, 10:49:59
Dupa cum vezi in enunt, la restrictii, se precizeaza ca sunt maxim 100 de teste (T<=100).  :)


Titlul: Răspuns: 002 Algoritmul lui Euclid extins
Scris de: Codrea Marcel din Martie 27, 2009, 13:50:27
prima mea pb rezolvata... am primit 100 pcte dar am creat acasa un fisier cu 100000 de numere si programul a terminat executia in 0.6 secunde pt datele din acest fisier (am cronometrat). deci depaseste timpul de executie din pb si totusi... am primit punctaj maxim

Daca te referi la sursa asta  (http://infoarena.ro/job_detail/289904?action=view-source)cred ca voiai sa scrii aici  aici (http://infoarena.ro/forum/index.php?topic=2759.0).
In ceea ce priveste diferenta dintre timpii de executie de acasa si cei de pe infoarena, trebuie sa stii ca evaluatorul  (http://infoarena.ro/documentatie/evaluator)infoarena ruleaza pe Linux unde timpii de evaluare sunt considerabil mai mici si in plus poate are o configuratie diferita de cea a PC-ului tau.


Titlul: Răspuns: 002 Algoritmul lui Euclid extins
Scris de: Moldovan Marcel din Martie 30, 2009, 11:46:06
prima mea pb rezolvata... am primit 100 pcte dar am creat acasa un fisier cu 100000 de numere si programul a terminat executia in 0.6 secunde pt datele din acest fisier (am cronometrat). deci depaseste timpul de executie din pb si totusi... am primit punctaj maxim

Daca te referi la sursa asta  (http://infoarena.ro/job_detail/289904?action=view-source)cred ca voiai sa scrii aici  aici (http://infoarena.ro/forum/index.php?topic=2759.0).
In ceea ce priveste diferenta dintre timpii de executie de acasa si cei de pe infoarena, trebuie sa stii ca evaluatorul  (http://infoarena.ro/documentatie/evaluator)infoarena ruleaza pe Linux unde timpii de evaluare sunt considerabil mai mici si in plus poate are o configuratie diferita de cea a PC-ului tau.
mersi pt raspuns  :D si scuze de greseala, dar cand am dat click pe "Lasa un comentariu" am ajuns la pagina asta de forum


Titlul: Răspuns: 002 Algoritmul lui Euclid extins
Scris de: Porumbel Valentin din Aprilie 11, 2009, 17:09:04
Cod:
Non-zero exit status.
Conditia asta unde trebuie pusa ?


Titlul: Răspuns: 002 Algoritmul lui Euclid extins
Scris de: Florian Marcu din Aprilie 11, 2009, 20:36:46
Cod:
Non-zero exit status.
Conditia asta unde trebuie pusa ?

Nu e conditie. Este un doar unul din mesajele returnate de evaluator.  :-k


Titlul: Răspuns: 002 Algoritmul lui Euclid extins
Scris de: Porumbel Valentin din Aprilie 13, 2009, 22:13:17
Pai pentru asta eu iau 0 puncte. :(


Titlul: Răspuns: 002 Algoritmul lui Euclid extins
Scris de: alexandru din Mai 08, 2009, 13:19:30
Citat
Non-zero exit status
Din cate stiu eu dupa terminare un program returneaza 0 -daca executarea s-a incheiat cu bine si diferit de 0 altfel


Titlul: Răspuns: 002 Algoritmul lui Euclid extins
Scris de: Pripoae Teodor Anton din Mai 08, 2009, 16:11:09
Omul a codat in pascal. Pascalul, din cate stiu eu, cand sunt greseli (deschide fisier inexistent pentru citire, face overflow la variabile, etc), returneaza numarul erorii ca exit code, si inchide programul. In cazul de fata, el a deschis fisierele euclid.in/euclid.out in loc de euclid2.in/euclid2.out. Aici e greseala.


Titlul: Răspuns: 002 Algoritmul lui Euclid extins
Scris de: Mihai Alex Ionescu din Iulie 06, 2009, 23:29:03
Salutare,
Am luat si eu 100 la aceasta problema dar tot am o nelamurire.
Daca folosesc euclid extins si inmultesc apoi cu c / cmmdc
De ce tot timpul solutiile se incadreaza in +/-2 miliarde ? pt a si b foarte mari adica, e vreun rationament matematic implicat?  Adica asa se intampla, dar nu imi dau seama de ce :-'

si exista vreo metoda prin care sa  aflu de ex  solutiile ecuatiei ax + by = c de modul minim?


Titlul: Răspuns: 002 Algoritmul lui Euclid extins
Scris de: Prigoana Cristian din Noiembrie 04, 2009, 10:29:48
imi zice   Solutie gresita la ecuatia 8 (30 -80 350) si rezultatul afisat ii 1 -4, de ce nu e corect ? :eyebrow: si la mai multe face asa ...  http://infoarena.ro/job_detail/361212


Titlul: Răspuns: 002 Algoritmul lui Euclid extins
Scris de: S. Alex din Februarie 02, 2010, 17:29:12
am si eu doua nelamuriri ..
prima: de ce daca c divide pe d , si NUMAI atunci exista solutii pentru ecuatie? daca .. sa presupun asa.. matematic ca exista un t pt care a*x + b*y = t ... (care este mai mic decat d, dar nu neaparat cred ).. in cazul in care exista atunci poate c nu se divide la d, dar se divide la t.. si ecuatia ar avea solutii.. astept va rog care aveti idei un argument pt chestia asta.. ca eu nu inteleg treaba asta, in rest am inteles totul ( cred ) foarte bine.. intradevar exista un d, d fiind cmmdc care sa rezolve ecuatia a*x + b*y .. bun dar de ce nu ar exista si alte valori dupa care sa ne luam? Adica nu inteleg de ce ne legam neaparat de cmmdc... daca pur si simplu exista (caci sigur exista ) alte valori diferite de d, egale cu a*x+b*y... si problema s-ar pune la acele valori care il divid pe c, in timp ce cmmdc(a,b) nu ar divide pe c, ar exista o solutie ..sper ca ma intelgeti careva.. imi transpun greu gandurile.. Problema am rezolvat-o de 100 de puncte, considerand cele spuse la indicatii ca fiind adevarate.. dar as vrea o mica demonstratie matematica, un argument ceva, sa fiu eu convins... pt ca nu sunt pe deplin convins ca cele presupuse pt rezolvare sunt adevarate..

a doua nelamurire: De ce indicatiile ne spun sa folosim algoritmul lui euclid extins, iar in exemple, se dau ca si solutii altele decat solutiile obtinut cu acest algoritm ? Eu unul am aplicat algoritmul si am obtinut solutii total diferite ( bune si ele,pt ca am luat 100, precum si alea din exemple ) insa nu inteleg.. ce algoritm s-a folosit pt determinarea solutiilor din exemple? ( presupun ca altul, ca euclid extins da pt valorile alea altceva )
multumesc anticipat.. sper sa intelegeti ce vroiam sa zic..


Titlul: Răspuns: 002 Algoritmul lui Euclid extins
Scris de: Ilie Ionut din Februarie 02, 2010, 18:10:22
1) In enunt scrie:
Citat
In cazul in care c nu se divide cu d ecuatia nu poate fi rezolvata in multimea numerelor intregi
Intotdeauna exista o infinitate de solutii.
Daca notam d=cmmdc(a,b), prod1=a/d, prod2=b/d, inseamna ca prod1,prod2 sunt intregi si avem
a*x+b*y=c
prod1*d*x+prod2*d*y=c
d*(prod1*x+prod2*y)=c
Daca d nu il divide pe c, atunci numarul c/d nu o sa fie intreg, ceea ce inseamna ca cel putin unul din numerele prod1*x si prod2*y apartine lui Q\Z, si cum prod1 si prod2 sunt din Z, inseamna ca ecuatia nu admite solutii intregi.

2) In enunt scrie:
Citat
In cazul in care exista mai multe solutii pentru o ecuatie, se poate afisa oricare solutie pentru care necunoscutele nu depasesc in valoare absoluta 2 000 000 000
Algoritmul lui Euclid extins e doar o metoda prin care poti sa afli o solutie a ecuatiei intotdeauna cand exista (in Z). Tu poti sa folosesti si un algoritm brut, dar nu o sa iei punctajul maxim.


Titlul: Răspuns: 002 Algoritmul lui Euclid extins
Scris de: S. Alex din Februarie 02, 2010, 18:34:23
1) da.. asa e .. corect.. in enunt era numa specificat stii .. dar asa e totul clar si demonstrat frumos ca e adevarat...
2) pai da corect lol dar nu ti se pare putin ilogic? tocmai ca zice ca alte variante nu or sa obtine punctaj maxim, atunci de ce ar da solutiile de la alti algoritmi? chiar nu mi se pare deloc logic.. acuma noah in fine .. is exemple is corecte nu ai ce sa zici .. dar din moment ce se indica o metoda si se zice ca ar exista altele dar nu intocmai bune pt ca sa intre in timp si etc pai e logic sa dai exemple cu solutii pe metoda aia.. altfel noah.. toata chestia e ca , eu unul cel putin mi-am batut  capu destul de mult timp sa vad de ce nu imi da mie bine, ca eu luam exemplele alea drept sfante .. mi-o luat  ceva sa imi dau seama, si ceva imi spune ca nu doar eu ..

ma rog, multumesc pentru lamuriri..  :ok:


Titlul: Răspuns: 002 Algoritmul lui Euclid extins
Scris de: Simoiu Robert din Februarie 02, 2010, 18:40:41
1) da.. asa e .. corect.. in enunt era numa specificat stii .. dar asa e totul clar si demonstrat frumos ca e adevarat...
2) pai da corect lol dar nu ti se pare putin ilogic? tocmai ca zice ca alte variante nu or sa obtine punctaj maxim, atunci de ce ar da solutiile de la alti algoritmi? chiar nu mi se pare deloc logic.. acuma noah in fine .. is exemple is corecte nu ai ce sa zici .. dar din moment ce se indica o metoda si se zice ca ar exista altele dar nu intocmai bune pt ca sa intre in timp si etc pai e logic sa dai exemple cu solutii pe metoda aia.. altfel noah.. toata chestia e ca , eu unul cel putin mi-am batut  capu destul de mult timp sa vad de ce nu imi da mie bine, ca eu luam exemplele alea drept sfante .. mi-o luat  ceva sa imi dau seama, si ceva imi spune ca nu doar eu ..

ma rog, multumesc pentru lamuriri..  :ok:
Eu nu cred ca solutiile le-or determinat cu algoritm, cred ca au fost puse rezolvari pe care le-au luat ei (adica ei au pus in fisierul de intrare valori care stiau rezultatul, si l-au scris in fisierul de iesire fara sa mai ruleze programul) sau au facut brute force pentru ca sunt mai multe solutii si asa sa le ia pe fiecare :)


Titlul: Răspuns: 002 Algoritmul lui Euclid extins
Scris de: Savin Tiberiu din Februarie 03, 2010, 12:34:06
eu luam exemplele alea drept sfante .. mi-o luat  ceva sa imi dau seama, si ceva imi spune ca nu doar eu ..

Nu e bine sa pui accent prea mare pe exemple. In general nici pe infoarena, nici la olimpiada, nu vei gasi exemple foarte bune. Vei primi niste exemple care sa nu te ajute in mare cu absolut nimic, decat sa intelegi cat de cat problema.


Titlul: Răspuns: 002 Algoritmul lui Euclid extins
Scris de: S. Alex din Februarie 03, 2010, 15:06:13
asa e doar ca intr-un an .. la olimpiada.. o fost dat la o problema enuntu gresit si exemplu corect.. enuntul corect a ajuns destul de tarziu la elevi asa ca cei care s-au luat dupa exemplu au avut un mare avantaj.. si oricum cand faci orice problema e normal sa testezi pe exemplu dat si sa te alarmezi daca nici macar ala nu iti da bine, nu? dar da e adevarat exemplu e doar un exemplu..


Titlul: Răspuns: 002 Algoritmul lui Euclid extins
Scris de: Simoiu Robert din Februarie 03, 2010, 15:14:34
Stii cum se spune: un exemplu te poate ajuta, dar in acelasi timp "deruta". Sunt probleme in care exemplul este un fel de "caz particular" , iar tu tratezi fara sa vrei acel caz, iar de restul uiti, si asa s-a dus problema de rapa  :angry:


Titlul: Răspuns: 002 Algoritmul lui Euclid extins
Scris de: Deea Andreea din Februarie 13, 2010, 17:21:25
Salut

Ma chinui de o juma de ora....
Asta e codul meu pt care primesc 0 puncte
Ce nu e bine?

Cod:
#include<iostream.h>
#include <fstream.h>
int eucl(int a, int b)
{
    if(a==b) return a;
    if(a>b)
           return eucl(a-b,b);
    else
        return eucl(a,b-a);
}
int main()
{
    int a,b,minim;
    ifstream fisin("euclid.in");
    fisin>>a;fisin>>b;
    fisin.close();
    ofstream fisout("euclid.out");
    fisout<<eucl(a,b);
 
   
   fisout.close();
}

 Foloseste [ code ] ... [/ code ] cand postezi cod.


Titlul: Răspuns: 002 Algoritmul lui Euclid extins
Scris de: GIgi ion din Martie 17, 2010, 15:31:15
Cod:
// algoritmul lui euclid.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include<iostream>
using namespace std;
#include<fstream>
ifstream f("euclid2.in.txt");
ofstream g("euclid2.out.txt");
int cmmdc(int a, int b)
{  int r;
    r = a % b;
      while(r != 0)
       {
         a = b;
         b = r;
         r = a % b;
      }
  return b;
}

int _tmain(int argc, _TCHAR* argv[])
{ int n,i,a,b;
f>>n;
cout<<n;
for(i=0;i<n;i++)
{
f>>a;f>>b;
cout<<a<<" ,"<<b;
g<<cmmdc(a,b);
g<<endl;
}

f.close();
g.close();
return 0;
}


Folosesc VIsual c++ 2008 ....ce este gresit de nu imi da 0 puncte?, Asta e prima data cand trimit o solutie la vreo problema si nu prea stiu cum merg lucrurile!


Titlul: Răspuns: 002 Algoritmul lui Euclid extins
Scris de: alexandru din Martie 17, 2010, 15:58:44
stdafx.h trebuie eliminat, aceasta biblioteca are sens doar pt IDE-ul folosit de tine si app taie iostream ( inutil ) si pune fstream in loc ;) ( desi l-ai pus sub namespace std; ) si este main nu _tmain :)
ps: ai gresit fisierele ( fara .txt )
pss: problema apartie de algoritmul lui euclid, nu de algoritmul lui euclid extins ;)


Titlul: Răspuns: 002 Algoritmul lui Euclid extins
Scris de: GIgi ion din Martie 17, 2010, 18:24:21
mersi, pai eu am dat sa dau comentariu aici http://infoarena.ro/problema/euclid2 (http://infoarena.ro/problema/euclid2) si vad ca l-a afisat aici , stiu ca nu trebuie <iostream> dar din obisnuinta... :aha: Thx!
Ps. De unde sa invat algoritmii de baza,? adica ce e prin manuale mi se pare putin...este vreo carte mai buna despre algoritmi?(nu vreau sa nu fie nici prea abstracta:D pentru ca nu stiu cat de mult am sa inteleg.)



Titlul: Răspuns: 002 Algoritmul lui Euclid extins
Scris de: alexandru din Martie 17, 2010, 18:28:52
Incearca setul de 3 volume : Programare  in limbajul C/C++ pentru liceu de Emanuela Cerchez si Marinel Serban. Primul volum e pentru incepatori( clasa a 9-10 ), al doilea volum e pentru clasa 10-11, iar ultimul pentru 11-12 :)


Titlul: Răspuns: 002 Algoritmul lui Euclid extins
Scris de: GIgi ion din Martie 17, 2010, 18:33:26

Mersi, vad ca nu imi ia decat 40 de puncte...si e facut prin impartire...de ce?:D
am facut si recursiv...dar tot nu trece de 40... ](*,)
Cod:
int cmmdc(int a, int b)
{  if (b==0)
return a;
else
return cmmdc(b,a%b);

}


Titlul: Răspuns: 002 Algoritmul lui Euclid extins
Scris de: Vlad Eugen Dornescu din Aprilie 02, 2010, 17:30:55
problema ar putea fi ca tu afisezi 1 daca sunt prime intre ele , in loc sa afisezi 0 cum scrie in enunt

L.E : vad ca s-a rezolvat


Titlul: Răspuns: 002 Algoritmul lui Euclid extins
Scris de: Simoiu Robert din Aprilie 02, 2010, 17:33:06
problema ar putea fi ca tu afisezi 1 daca sunt prime intre ele , in loc sa afisezi 0 cum scrie in enunt
Vezi tu undeva scris asa ceva ? NU mai posta aiurea, ca incurci oamenii .


Titlul: Răspuns: 002 Algoritmul lui Euclid extins
Scris de: Ilinca Ciprian din Aprilie 13, 2010, 19:45:03
Cod:

Cod:
include<stdio.h>
int main()
{
 freopen("euclid2.in","r",stdin);
 freopen("euclid2.out","w",stdout);
  int aux,a,b,i,x;
  for(i=0;i<x;i++)
    {
      scanf("%d",&a);
      scanf("%d",&b);
    }

    while(b!=0)
     {
       aux = b;
       b = a%b;
       a = aux;


     }
  printf("%d",a);
  printf("\n");

 return 0;
}

Modificat de Moderator : Foloseste tag-ul [ code ] ... [/ code ] pentru surse!


imi spune si mie cineva de ce imi afiseaza 2?


Titlul: Răspuns: 002 Algoritmul lui Euclid extins
Scris de: alexandru din Aprilie 13, 2010, 19:48:33
aux=a%b;
Nu inteleg ce are de a face cu Algoritmul lui Euclid Extins


Titlul: Răspuns: 002 Algoritmul lui Euclid extins
Scris de: Simoiu Robert din Aprilie 13, 2010, 19:48:47
Cod:
for(i=0;i<x;i++)
    {
      scanf("%d",&a);
      scanf("%d",&b);
    }
Asta ce este ? X este un numar random, pentru ca este in interiorul int-ului, si de accea b si a vor fi iarasi numere random, si probabil daca rulezi de mai multe ori o sa ai rezultat diferit.
Incearca asa:
Cod:
include<stdio.h>
int main()
{
 freopen("euclid2.in","r",stdin);
 freopen("euclid2.out","w",stdout);
  int aux,a,b,i;

    scanf("%d",&a);
    scanf("%d",&b);
   
    while(b!=0)
     {
       aux = b;
       b = a%b;
       a = aux;


     }
  printf("%d",a);
  printf("\n");

 return 0;
}

EDIT: Alexandru, daca te uiti atent ALE si ALE Extins au acelasi post daca dai la comentarii, am postat la cel simplu pe forum dar nu mi-a raspuns nimeni.


Titlul: Răspuns: Algoritmul lui Euclid
Scris de: Ilinca Ciprian din Aprilie 13, 2010, 19:54:42
Imi da la fel ](*,)


Titlul: Răspuns: 002 Algoritmul lui Euclid extins
Scris de: George Popoiu din Aprilie 13, 2010, 21:22:12
@cipri20 M-am uitat pe sursa ta si calcularea cmmdc e corecta, doar ca tu nu tii cont ca in fisierul de intrare vor fi T teste. Si cred ca e nevoie de long long pentru 100pt.

Sper ca ti-a fost de folos.


Titlul: Răspuns: 002 Algoritmul lui Euclid extins
Scris de: Simoiu Robert din Aprilie 13, 2010, 21:26:18
@popoiu.george E suficient int , incape
@cipri20 Trebuie sa citesti prima data pe T si apoi sa faci un for in care de fiecare data calculezi cmmdc
Cod:
scanf("%d",&T);
for (i = 1; i <= T; i++)
       scanf("%d %d", &a,&b);
       ......................


Titlul: Răspuns: 002 Algoritmul lui Euclid extins
Scris de: Ilinca Ciprian din Aprilie 14, 2010, 17:06:50
 
Cod:
  #include<stdio.h>
int main()
{
 int i,a,b,r,T;
 freopen("euclid2.in","r",stdin);
 freopen("euclid2.out","w",stdout);
  scanf("%d",&T);
  for(i=1;i<=T;i++)
   scanf("%d %d",&a,&b);
    do
      {
    r=a%b;
    a=b;
    b=r;
      }while(r!=0);

    printf("%d\n",a);
   return 0;
}
imi afiseaza 1 de fiecare data  ](*,)

si daca faca
Cod:
  while(b>0)
    {
      ....
    }
la fel afiseaza
Modificat de Moderator: Nu mai posta de 2 ori consecutiv. Foloseste butonul "Modifica".


Titlul: Răspuns: 002 Algoritmul lui Euclid extins
Scris de: Mircea Dima din Aprilie 14, 2010, 17:37:12
Cod:
  #include<stdio.h>
int main()
{
 int i,a,b,r,T;
 freopen("euclid2.in","r",stdin);
 freopen("euclid2.out","w",stdout);
  scanf("%d",&T);
  for(i=1;i<=T;i++)
   scanf("%d %d",&a,&b);
    do
      {
    r=a%b;
    a=b;
    b=r;
      }while(r!=0);

    printf("%d\n",a);
   return 0;
}
imi afiseaza 1 de fiecare data  ](*,)

si daca faca
Cod:
  while(b>0)
    {
      ....
    }
la fel afiseaza
Modificat de Moderator: Nu mai posta de 2 ori consecutiv. Foloseste butonul "Modifica".


Tu doar citesti in for... nu si calculezi cmmdc-ul.
Ar trebui sa faci asa (observa acoladele):

Cod:

for(i=1;i<=T;i++)
{
   scanf("%d %d",&a,&b);
    do
      {
    r=a%b;
    a=b;
    b=r;
      }while(r!=0);
     printf ("%d\n", a);
}


Titlul: Răspuns: 002 Algoritmul lui Euclid extins
Scris de: Ilinca Ciprian din Aprilie 14, 2010, 20:55:43
Mersi mult mi-a iesit :winner1:


Titlul: Răspuns: 002 Algoritmul lui Euclid extins
Scris de: Paul Buda din August 26, 2010, 14:09:58
dece pe calculatorul meu pe exemplul lor am rezultatele
98 -147
13 -13
0 0

si cand am trimis sursa am luat 100 de puncte ????
nu inteleg imi poate explica cineva


Titlul: Răspuns: 002 Algoritmul lui Euclid extins
Scris de: Simoiu Robert din August 26, 2010, 14:27:34
Citat
In cazul in care exista mai multe solutii pentru o ecuatie, se poate afisa oricare solutie pentru care necunoscutele nu depasesc in valoare absoluta 2 000 000 000. Pentru toate ecuatiile pentru care exista solutie, va exista si o solutie cu ambele necunoscute aflate in acest interval.
Deci inseamna ca rezultatul dat de tine e bun ....
P.S. - Atat imi da si mie :P


Titlul: Răspuns: 002 Algoritmul lui Euclid extins
Scris de: Paul Buda din August 26, 2010, 14:43:02
ioi am am sarit peste partea aceea ms :))


Titlul: Răspuns: 002 Algoritmul lui Euclid extins
Scris de: Andrei Alexandrescu din Septembrie 22, 2010, 18:13:31
Poate cineva, va rog, sa imi spuna de ce cand imi declar variabilele long long nu iau 100 si cand le declar int iau 100?

Sursa 100: http://infoarena.ro/job_detail/486775
Sursa 0: http://infoarena.ro/job_detail/486766

Multumesc anticipat!


Titlul: Răspuns: 002 Algoritmul lui Euclid extins
Scris de: Petru Trimbitas din Septembrie 22, 2010, 18:44:53
Incearca sa folosesti %lld in loc de %I64d


Titlul: Răspuns: 002 Algoritmul lui Euclid extins
Scris de: FMI Trifan Mircea Mihai din Martie 21, 2012, 00:58:42
Am inteles partea cu daca c%d != 0 atunci nu exista solutii dar ma incurc la celalalt caz: de ce trebuie sa inmultim x si y cu (c/d) ca sa obtinem solutie?


Titlul: Răspuns: 002 Algoritmul lui Euclid extins
Scris de: Bosinta Alexandru din Martie 30, 2015, 15:57:05
O intrebare: care e diferenta in a folosi &X sau X in functia din exemplu?


Titlul: Răspuns: 002 Algoritmul lui Euclid extins
Scris de: Witsel Andrei din Aprilie 02, 2015, 12:29:34
Bosinta Alexandru.
Diferenta e ca atunci cand folosesti & , X care a apelat functia se modifica in functie de X din functie.
 
un exemplu:
void functie(int &x)
{
    x=5;
}
int main()
{
    int x=1;
    functie(x)
    cout<<x; // x va fi 5.
}


Titlul: Răspuns: 002 Algoritmul lui Euclid extins
Scris de: Ciubotaru Adina-Maria din Mai 16, 2015, 12:32:49
De ce atunci cand declar variabilele global iau 100 si daca le declar local iau 50  :oops: ?
http://www.infoarena.ro/job_detail/1436740?action=view-source
http://www.infoarena.ro/job_detail/1436782?action=view-source


Titlul: Răspuns: 002 Algoritmul lui Euclid extins
Scris de: Bogdan Boboc din Mai 16, 2015, 23:13:34
De ce atunci cand declar variabilele global iau 100 si daca le declar local iau 50  :oops: ?
http://www.infoarena.ro/job_detail/1436740?action=view-source
http://www.infoarena.ro/job_detail/1436782?action=view-source

uite aici http://www.infoarena.ro/job_detail/1437152?action=view-source

la linia 34 ai uitat sa pui parantezele
Cod:
else g<<x*c/d<<' '<<y*c/d<<'\n';

Cod:
else g<<x*(c/d)<<' '<<y*(c/d)<<'\n';


Titlul: Răspuns: 002 Algoritmul lui Euclid extins
Scris de: Ciubotaru Adina-Maria din Mai 18, 2015, 19:55:28
Multumesc. Asa e.  ](*,)


Titlul: Răspuns: 002 Algoritmul lui Euclid extins
Scris de: Alin Pisica din Noiembrie 09, 2015, 15:36:42
La testul de intrare oferit ca exemplul, rezultatele pe care le-ati dat in testul de iesire sunt gresite  #-o .


Titlul: Răspuns: 002 Algoritmul lui Euclid extins
Scris de: Alexandru Valeanu din Noiembrie 09, 2015, 18:20:30
Nu sunt greșite!
Răspunsul nu este unic!