Răspuns: 000 Algoritmul lui Euclid

[•stef2n]

Comentarii la articolul Algoritmul lui Euclid

[•soriyn]

Ce face functia assert ?

Cod:

assert( -1000000000 <= A && A <= 1000000000 );

[•Mishu91]

Dacă acea condiție din paranteză nu este îndeplinită execuția programului este întreruptă și dă un mesaj de eroare. Acea funcție este folosită de cei care adaugă problemele pentru a se asigura că sunt respectate toate restricțiile.

[•ucc_5]

Nu trebuia sa scrie aici " Daca b = 0, atunci a * 1 + b * 0....."  y=0 in loc de b=0?

[•ionutz32]

Nu, pentru ca acolo spune de capatul recurentei, unde b=0 si cmmdc=a, iar o solutie pentru a*x+b*y=d <=> a*x+0*y=a, e cand x=1 si y=0, pentru ca a*1+0*0=a.

[•alex_unix]

Ce complexitate are Euclid extins ?

[•blasterz]

Ce complexitate are Euclid extins ?

O(logn)

[•alex_unix]

Mersi

[•witsel]

de ce a%b=a-b*c?? a-b*c nu este 0??

[•SebiSebi]

Nu, nu este 0. a%b = a - b*[a/b] unde [ x ] reprezinta partea intreaga a numarului x. In C++ se executa operatiile pe int(default) dacă nu faci type casting. Daca scriai (double) a - b*(1.00*a/b) atunci asta era 0 mereu.

[•witsel]

aha, merci. poti sa-mi spui te rog de ce atunci cand ajungi la apelul lui euclid , de ce programul calculeaza si *x = y0;
*y = x0 - (a / b) * y0;. nu ar trebui sa apeleze din nou functia pana cand b==0, nemaitrecand la cele doua ecuatii care sunt dupa apel?
 euclid(b, a % b, d, &x0, &y0);
*x = y0;
*y = x0 - (a / b) * y0;

[•SebiSebi]

Nu înțeleg ce nelămurire ai. Mai explică odată te rog.

[•witsel]

nu inteleg cum ajunge programul sa rezolve ecuatiile "*x = y0; *y = x0 - (a / b) * y0;" , avand in vedere ca "euclid(b, a % b, d, &x0, &y0);" apeleaza functia inainte ca programul sa rezolve cele 2 ecuatii. Nu pot sa explic mai bine.. Daca nu ai inteles ce vreau... poti sa-mi explici cum "ruleaza" programul pas cu pas? ce face fiecare instructiune in parte?

[•SebiSebi]

Programul nu rezolvă cele două ecuații ci ecuația A * X + B * Y = D. Cele două atribuiri de care vorbești sunt explicate chiar în articol. Parametrii sunt pointeri tocmai pentru a putea folosi informațiile obținute din rezolvarea ecuației b * x0 + (a % b) * y0 = d;
Deci tu știi x0 și y0 și vrei să afli X si Y. Sunt o infinitate de posibilitati, una dintre ele este urmatoarea x = y0; y = x0 - (a / b) * y0.

[•witsel]

Deci.. am inteles in mare partea matematica. Nu am inteles totusi un lucru. Cat sunt X0 si Y0. Daca cu 1 respectiv 0, de ce ? pentru ca asta se intampla abia cand b=0, deci X o sa devina 0, iar Y 1, ceea ce nu e corect...

[•kosas]

exact...nici eu nu inteleg de ce la sfarsitul recurentei y=0.
Iar ,cand b=0,ecuatia a * x + b * y = d(cmmdc) devine a*1+0*y=a ceea ce e adevarat; deci y nu e musai 0. 

[•Mircea_Donciu]

Prostiii.         

[•AdiMuntean]

De ce, pentru Euclid extins, trei din cinci parametrii sunt pointeri? Cum influenteaza modul in care functioneaza algoritmul?