h1. Algoritmul lui Euclid
(Creat de ==user(user="fluffy" type="tiny")== la data de _2004-11-16_ categoria _Teoria numerelor_, autor(i) _Crestez Leonard_)
(Categoria _Matematica_, Autor _Leonard Crestez_)
O prezentare a variantei extinse a algoritmului lui Euclid, care rezolva ecuatie de forma {$A * X + B * Y = D$}, unde $D$ este cel mai mare divizor comun al lui $A$ si {$B$}. De asemenea este prezentata o aplicatie "interesanta": impartirea modulara.
==Include(page="template/raw")==
Probabil ca multi stiti algoritmul lui Euclid de prin clasa a 5-a, cand invatati la matematica divizibilitate. Varianta simplista a algoritmului lui Euclid este cunoscuta de multa lume, dar fara prea multe explicatii despre functionarea lui.
h2. Euclid simplu
In cuvinte, algoritmul pur si simplu impare deimpartitul la rest pana cand impartitorul este {$0$}, apoi returneaza deimpartitul. Poate fi usor implementat iterativ in C. Probabil ca aceasta forma este si cea mai rapida, si este de preferat cand nu e necesar Euclid extins.
In cuvinte, algoritmul pur si simplu imparte deimpartitul la rest pana cand impartitorul este {$0$}, apoi returneaza deimpartitul. Poate fi usor implementat iterativ in C. Probabil ca aceasta forma este si cea mai rapida, si este de preferat cand nu e necesar Euclid extins.
== code(c) |
int euclid(int a, int b)
== code(c) | int euclid(int a, int b)
{
int c;
while (b) {
}
==
Sa vedem cum functioneaza algoritmul lui Euclid. Se observa ca daca {$a< b$}, atunci $euclid(b, a % b)$ este de fapt {$euclid(b, a)$}.
Sa vedem cum functioneaza algoritmul lui Euclid. Se observa ca daca {$a<b$}, atunci $euclid(b, a % b)$ este de fapt {$euclid(b, a)$}.
Vom demonstra ca {$cmmdc(a, b) = cmmdc(b, a % b)$}. Notam $cmmdc(a, b)$ cu {$d$}. Scriem $a%b$ drept {$a - b * c$}, unde $c$ este parte intreaga din {$a / b$}. Cum $a$ si $b$ sunt divizibile cu {$b$}, atunci orice combinatie liniara a lor este divizibila cu {$d$}, inclusiv {$a - b * c = a %b$}.
Asta insa nu este de ajuns, putem aveam {$Z > d$}, $Z$ divizibil cu {$d$}, care sa fie {$cmmdc(b, a % b)$}. Insa atunci ar rezulta similar ca a e divizibil cu {$Z$}, deci {$Z = d = cmmdc(a, b)$}, Incalcand {$Z > d$}.
Vom demonstra ca {$cmmdc(a, b) = cmmdc(b, a % b)$}. Notam $cmmdc(a, b)$ cu {$d$}. Scriem $a%b$ drept {$a - b * c$}, unde $c$ este parte intreaga din {$a / b$}. Cum $a$ si $b$ sunt divizibile cu {$d$}, atunci orice combinatie liniara a lor este divizibila cu {$d$}, inclusiv {$a - b * c = a%b$}.
Asta insa nu este de ajuns, putem avea {$Z > d$}, $Z$ divizibil cu {$d$}, care sa fie {$cmmdc(b, a % b)$}. Insa atunci ar rezulta similar ca a e divizibil cu {$Z$}, deci {$Z = d = cmmdc(a, b)$}, Incalcand {$Z > d$}.
Astfel, algoritmul lucreaza reducand problema la numere din ce in ce mai mici, pana cand {$a % b = 0$}. Ca sa finalizam recurenta, daca $a$ este divizibil cu {$b$}, atunci este evident ca {$cmmdc(a, b)$} este {$b$}. In cod este un pic mai "ciudat", prindem acest caz doar dupa inca un apel recurent, cand {$b = 0$}. De fapt cred ca $cmmdc$ este definit pe numere strict pozitive, dar in informatica putem ocoli un pic matematica.
h2. Euclid extins
Acest algoritm poate fi extins, in sensul gasirii $x$ si $y$ astfel incat {$a * x + b * y = d$}. In acest articol vom incerca sa deducem modul de calculare al lui x si y. Cei grabiti sau certati cu matematica pot sari direct la codul sursa, dar vor avea probleme in a tine minte algoritmul pe viitor.
Acest algoritm poate fi extins, in sensul gasirii $x$ si $y$ astfel incat {$a * x + b * y = d$}. In acest articol vom incerca sa deducem modul de calculare al lui $x$ si {$y$}. Cei grabiti sau certati cu matematica pot sari direct la codul sursa, dar vor avea probleme in a tine minte algoritmul pe viitor.
Vom extinde procedura recursiva de calculare a $cmmdc$ pentru a include si $x$ si {$y$}. Calculam $x$ si $y$ incepand de la "capatul recurentei". Daca {$b = 0$}, atunci $a * 1 + b * 0 = a(cmmdc)$ evident, asa ca initial $x = 1$ si {$y = 0$}. Incercam sa calculam {$x$}, $y$ in functie de {$x0$}, $y0$ obtinuti pentru {$b$}, {$a % b$}. Noi stim urmatoarele:
* $b * x0 + (a % b) * y0 = d$
* $a * x + b * y = d$
Trebuie sa aflam o solutie pentru $x$ si {$y$}. Vom nota ca mai sus parte intreaga din $a / b$ cu {$c$}.
* $b * x0 + (a - b * c) * y0 = a * x + b * y$
* $b * (x0 - c * y0 - y) = a * (x - y0)$
O solutie este acum evidenta (Una, sunt o infinitate de perechi {$x, y$})
* {$x0 - c * y0 - y = 0$}, De unde rezulta $y = x0 - c * y0$
* {$x - y0 = 0$}, De unde rezulta $x = y0$
Vom extinde procedura recursiva de calculare a cmmdc pentru e include si x si y. Calculam x si y incepand de la "capatul recurentei". Daca b = 0, atunci a * 1 + b * 0 = a(cmmdc) evident, asa ca initial x = 1 si y = 0. Incercam sa calculam x, y in functie de x0, y0 obtinuti pentru b, a % b. Noi stim urmatoarele:
b * x0 + (a % b) * y0 = d
a * x + b * y = d
Trebuie sa aflam o solutie pentru x si y. Vom nota ca mai sus parte intreaga din a / b cu c.
b * x0 + (a - b * c) * y0 = a * x + b * y
b * (x0 - c * y0 - y) = a * (x - y0)
O solutie este acum evidenta (Una, sunt o infinitate de perechi x, y)
x0 - c * y0 - y = 0, De unde rezulta y = x0 - c * y0
x - y0 = 0, De unde rezulta x = y0
Acum nu mai pare asa de "magic", nu?
Sursa modificata pentru a calcula si x si y nu este mult mai complexa. Acum intelegeti de ce am trimis d ca pointer mai sus, si de ce am folosit varianta recursiva a algoritmului lui euclid. Implementat iterativ, este nevoie de un vector care sa tina toate valorile c (a / b) obtinute pe parcurs.
Sursa modificata pentru a calcula si $x$ si $y$ nu este mult mai complexa. Acum intelegeti de ce am trimis $d$ ca pointer mai sus, si de ce am folosit varianta recursiva a algoritmului lui euclid. Implementat iterativ, este nevoie de un vector care sa tina toate valorile $c$ ({$a / b$}) obtinute pe parcurs.
Nota pentru pascalisti: in C nu exista div, impartirea intre int-uri este automat si impartire intreaga (div din pascal).
void euclid(int a, int b, int *d, int *x, int *y)
== code(c) | void euclid(int a, int b, int *d, int *x, int *y)
{
if (b == 0) {
*d = a;
*x = 1;
*y = 0;
} else {
int x0, y0;
euclid(b, a % b, d, &x0, &y0);
*x = y0;
*y = x0 - (a / b) * y0;
}
if (b == 0) {
*d = a;
*x = 1;
*y = 0;
} else {
int x0, y0;
euclid(b, a % b, d, &x0, &y0);
*x = y0;
*y = x0 - (a / b) * y0;
}
}
==
Impartire modulara
h2. Impartire modulara
Acum pentru o aplicatie interesanta, impartirea modulara. Nu voi intra in detalii, pe scurt aritmetica modulara este aritmetica in care toate valorile se iau modulo un anumit numar n. Spre exemplu, in modulo 7, 3 = 10. Similar, rezultatele tuturor operatiilor se iau in modul: 4 + 5 = 2, 3 * 5 = 1, etc.
Acum pentru o aplicatie interesanta, impartirea modulara. Nu voi intra in detalii, pe scurt aritmetica modulara este aritmetica in care toate valorile se iau modulo un anumit numar {$n$}. Spre exemplu, in {@modulo 7@},avem {$3 = 10$}. Similar, rezultatele tuturor operatiilor se iau in modul: {$4 + 5 = 2$}, {$3 * 5 = 1$} etc.
Cum putem defini insa impartirea in modulo? Evident, 6 / 2 este tot 3, dar3 / 4 cu cat este egal? De obicei impartirea este definita ca operatia inversa a inmultirii, similar cum scaderea este operatia inversa a adunarii. Astfel, daca a / b = c atunci b * c = a. Prin algoritmul lui Euclid putem afla x si y astfel incat n * x + b * y = cmmdc(n, b), unde n este modulul .Totul e modulo n, asa ca putem ignora x * n. Atunci c = y * a / cmmdc(n, b). Daca a nu este divizibil cu cmmdc(n, b), atunci c nu exista. Intradevar, nu exista c pentru care 3 * c = 4 modulo 6.
Cum putem defini insa impartirea in modulo? Evident, {$6 / 2$} este tot {$3$}, dar $3 / 4$ cu cat este egal? De obicei impartirea este definita ca operatia inversa a inmultirii, similar cum scaderea este operatia inversa a adunarii. Astfel, daca {$a / b = c$} atunci {$b * c = a$}. Prin algoritmul lui Euclid putem afla $x$ si $y$ astfel incat {$n * x + b * y = cmmdc(n, b)$}, unde $n$ este modulul. Totul e modulo {$n$}, asa ca putem ignora {$x * n$}. Atunci {$c = y * a / cmmdc(n, b)$}. Daca $a$ nu este divizibil cu {$cmmdc(n, b)$}, atunci $c$ nu exista. Intradevar, nu exista $c$ pentru care $3 * c = 4$ modulo {$6$}.
Tema pentru acasa
h2. Tema pentru acasa
Cateva probleme care se rezolva intr-un mod sau altul folosing algoritmul lui Euclid sau algoritmul lui Euclid extins:
[1]Sgu 106: The Equation
[2]Sgu 137: Funny Strings
[3]Sgu 141: Jumping Joe
[4]Sgu 248: Integer Linear Programming
References
Visible links
1. http://acm.sgu.ru/problem.php?contest=0&problem=106
2. http://acm.sgu.ru/problem.php?contest=0&problem=137
3. http://acm.sgu.ru/problem.php?contest=0&problem=141
4. http://acm.sgu.ru/problem.php?contest=0&problem=248
* Sgu 106: "The Equation":http://acm.sgu.ru/problem.php?contest=0&problem=106
* Sgu 137: "Funny Strings":http://acm.sgu.ru/problem.php?contest=0&problem=137
* Sgu 141: "Jumping Joe":http://acm.sgu.ru/problem.php?contest=0&problem=141
* Sgu 248: "Integer Linear Programming":http://acm.sgu.ru/problem.php?contest=0&problem=248
O sursa interesanta pentru Algoritmul lui Euclid este cea din cartea lui Knuth Arta Programarii Calculatoarelor Vol. 2 Algoritmi Seminumerici care descrie stransa legatura intre algoritm si fractiile continue (Cap. 4.5.3)
