Lectia 16

Cmmdc si Cmmc

Din punct de vedere matematic, cel mai mare divizor comun a două numere naturale a şi b este un număr natural d, care:

· divide şi pe a şi pe b:

· este divizibil cu orice divizor a lui a şi b.

Pentru a afla cel mai mare divizor comun al două sau mai multor numere naturale mai mari decât 1 se procedează astfel:

· se descompun numerele în factori primi

· se iau toţi factorii primi comuni, o singură dată, la puterea cea mai mică şi se înmulţesc între ei.

Exemplu:

Dacă a = 420 atunci descompunerea în factori primi este 420=2²*3*5*7 şi dacă b = 504 atunci descompunerea în factori primi este 504=2³*3²*7, de unde rezultă că cel mai mare divizor comun dintre cele două numere, notat cmmdc(420, 504)= 2²*3*7=84

Pentru a scrie un algoritm care determină valoarea celui mai mare divizor comun dintre două numere după modelul matematic de determinare este destul de complicat. Există algoritmi mai simpli pentru realizrea acestui lucru:

Algoritmul lui Euclid:

Varianta 1: Folosind operaţia de împărţire

Se citesc cele două numere naturale a şi b, iar în situaţia în care a nu este mai mare decât b se interschimbă valorile celor două variabile. Se împarte a la b pănă la obţinerea unui rest egal cu zero. Dacă restul obţinut în urma împărţirii lui a la b nu este zero atunci valoarea lui b va fi transferată în variabila a, valoarea restului va fi transferat în b si se va relua algoritmul prin calcularea restului împărţirii lui a la b, dar cu noile valori ale variabilelor a şi b. Valoarea celui mai mare divizor comun dintre a şi b, notată cmmdc(a,b), va fi egală cu ultimul rest diferit de zero(care va fi păstrat în variabila b)

Algoritmul în pseudocod este:

citeşte a,b // două numere naturale pentru care calculez cmmdc

┌dacă a<b atunci //interschimb valoarea lui acu valoarea lui b

│ aux=a

│ a=b

│ b=aux

└■

r=a%b // determin restul impartirii lui a la b

┌cât timp r≠ 0 execută

│ a=b

│ b=r

│ r=a%b

└■

scrie ”cmmdc dinte ”, a,” si ”, b, ” este ”,b //ultimul rest diferit de zero

Varianta 2: Folosind operaţia de scădere

Se citesc cele două numere naturale a şi b pentru care se doreşte să se calculeze valoarea celui mai mare divizor comun. Algoritmul în acest caz este mai simplu şi presupunerea scăderii variabilei de valoare mai mică din variabila de valoare mai mare, păstrând rezultatul obţinut în variabila din care am scăzut. Această operaţie de scădere repetată va continua în acealaşi mod cât timp valorile variabilelor a şi b sunt diferite. Valoarea comună la care se ajunge este chiar valoarea celui mai mare divizor comun dintre numerele date iniţial.

Algoritmul în pseudocod este:

citeşte a,b //două numere naturale pentru care calculez cmmdc

┌cât timp a ≠ b execută //dacă numerele sunt diferite atunci până când ajung

│ //egale din cel mai mare numar il scad pe cel mai mic

│ ┌dacă a > b atunci

│ │ a = a-b

│ │altfel

│ │ b = b-a

│ └■

└■

scrie ”cmmdc dinte ”,a,” si ”,b,” este ”,a //valoarea comuna dintre a si b

Două sau mai multe numere naturale care au cel mai mare divizor comun al lor egal cu 1 se numesc numere prime între ele.

Matematic, cel mai mic multiplu comun a două numere naturale a şi b este un număr natural m, care:

· este multiplu al lui a şi al lui b;

· se divide cu orice multiplu al numerelor a şi b.

Cel mai mic multiplu comun dintre două numere naturale a şi b, notat cmmmc(a,b) se calculează cu relaţia:

deci algoritmul de determinare a cmmmc(a,b) este:a*b/cmmdc(a,b)

citeşte a,b // numere naturale

// determină cmmdc(a,b) cu una din variantele Algoritmului lui Euclid

scrie ”cmmdc dintre”, a, ” si ”, b, ” este:”

c=a*b

//deoarece valorile iniţiale ale variabilelor a şi b se alterează după //rularea algoritmului lui Euclid voi calcula produsul lor inainte de a le

//strica valoarea

┌cât timp a ≠ b execută

│ ┌dacă a > b atunci

│ │ a = a-b

│ │altfel

│ │ b = b-a

│ └■

└■

scrie c/a //a=b după incheierea algoritmului de determinare a cmmdc si

//reprezinta chiar valoarea determinată

[1] „Algoritmul lui Euclid este străbunicul tuturor algoritmilor, deoarece este cel mai vechi algoritm netrivial care a supravieţuit până în ziua de azi.”Donald Knuth, The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, 2nd edition (1981), p. 318.