CMMDC Si CMMMC

Informatică & TIC
sites.google.com/site/stanciu4info4tic/home/clasa-ix/cmmdc-si-cmmc
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=22*3*5*7 şi dacă b =

504 atunci descompunerea în factori primi este 504=23*32*7, de unde rezultă că cel
mai mare divizor comun dintre cele două numere, notat cmmdc(420, 504)=
22*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
│
1/3
│ 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;
2/3
· 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.
3/3

CMMDC Si CMMMC

Încărcat de

Drepturi de autor:

Formate disponibile

CMMDC Si CMMMC

Încărcat de

Informații document

Descriere originală:

Titlu original

Drepturi de autor

Formate disponibile

Partajați acest document

Partajați sau inserați document

Opțiuni de partajare

Vi se pare util acest document?

Este necorespunzător acest conținut?

Drepturi de autor:

Formate disponibile

CMMDC Si CMMMC

Încărcat de

Drepturi de autor:

Formate disponibile

Informatică & TIC

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

· se descompun numerele în factori primi

Dacă a = 420 atunci descompunerea în factori primi este 420=22*3*5*7 şi dacă b =

Algoritmul lui Euclid:

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

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

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

┌cât timp r≠ 0 execută

Varianta 2: Folosind operaţia de scădere

Algoritmul în pseudocod este:

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

│ ┌dacă a > b atunci

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

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:”

//deoarece valorile iniţiale ale variabilelor a şi b se alterează după //rularea

┌cât timp a ≠ b execută

│ ┌dacă a > b atunci

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

//reprezinta chiar valoarea determinată

S-ar putea să vă placă și

Dacă a = 420 atunci descompunerea în factori primi este 420=2235*7 şi dacă b =