L11. Cmmdc. Cmmmc

C.m.m.d.c. este acronimul (prima litera de la fiecare cuvant) de la "cel mai mare divizor comun" si se aplica pentru doua numere naturale.

Problema. Fie doua numere naturale A si B. Sa se determine cel mai mare divizor comun a lui A si B.

Sa citim iar. Practic trebuie sa determin un numar natural care sa fie divizor atat pentru A cat si pentru B. Daca sunt mai multe numere in aceasta situatie, atunci il aleg pe cel mai mare. Ceea ce ma duce cu gandul la

Varianta 1.

citeste A, B; 

cmmdc=0;

pentru D=1 pana la A executa

       daca (A%D==0 si B%D==0 ) atunci cmmdc=D;

scrie cmmdc;

Practic, cmmdc-ul va fi cel mult unul dintre numere. As putea sa fiu prevazator si sa aleg ca limita superioara pe cel mai mic dintre A si B. Si conditia de numitor comun se poate rescrie A%D +B%D==0.

Varianta 2.

citeste A,B

min=A; daca (min>B) atunci min=B;

pentru D=1 pana la min executa

       daca (A%D +B%D==0) atunci cmmdc=D;

scrie cmmdc;

Varianta 3.

Problema nu e noua, Euclid (cca 325 - 265 î.Hr.!!!!!) s-a gandit si el la acelasi lucru si a gasit o solutie. Daca D este divizorul comun a lui A si B, atunci estista A2 si B2 asa incat:

• A=D*A2


• B=D*B2 si deduce ca si diferenta acestor numere are acelasi divizor comun


• A-B=D*(A2-B2)

Practic, in "lenea" lui de a calcula cmmdc(A,B), Euclid propune mereu o pereche mai mica (A-B, B) daca A>B sau (A, B-A) daca B>A. Deci, cmmdc(A, B) este

• (A-B, B) daca A>B


• (A, B-A) daca B>A


• A daca A==B

Se observa ca in primele doua cazuri trebuie sa reluam algoritmul, ceea ce ne duce cu gandul la urmatoarea secventa:

citeste A,B

cat timp (A!=B) executa

daca (A>B) atunci A=A-B;

            altfel B=B-A;

scrie A;

Varianta 4.

Deci varianta 3 e de acum 2000 de ani! Intre timp, s-a mai facut o varianta. Daca A=23456 si B=89 ar trebui sa se efectueze o multime de scaderi a lui B din A. Scaderi repetate, pana nu se mai poate scadea pe B din A! Asta este o impartire si ce ramane in A este restul. In consecinta, pe cel mai mare il vom transforma in restul impartirii. Cand ne oprim? Ne vom opri cand A sau B vor fi nule, ceea ce inseamna ca cealalta valoare, nenula, va fi CMMDC.

citeste A,B;

cat timp (A*B!=0) executa //daca nici unul nu e nul....


daca (A>B) atunci A=A%B;

            altfel B=B%A;

scrie A+B; //afisez valoarea nenula


Varianta 5.

Desi varianta 4 e o solutie respectabila, inca nu e de ajuns. Practic, la fiecare iteratie se executa 2 teste - cel din CAT TIMP si cel din DACA. Varianta urmatoare foloseste aceeasi idee de mai sus dar elimina unul din teste.

citeste A,B;

cat timp (B!=0) executa


{R=A%B; A=B; B=R;}

scrie B;

Analiza variantelor

Evident, ultima varianta este cea mai buna. Am explicat deja ratiunile prin care s-a trecut de la o varianta la alta. In vederea examenului de bacalaureat va trebuie toate variantele, indeosebi ultima pentru momentul cand va trebui sa programati.

 

Calculul CMMMC

Pentru calculul matematic a cmmdc pentru doua numere A si B, se realizeaza descompunerea in factori primi si apoi se considera termenii comuni, la puterea cea mai mica.

Pentru calculul matematic a cmmmc pentru doua numere A si B, se realizeaza descompunerea in factori primi si apoi se considera termenii comuni si necomuni, la puterea cea mai mare.

Practic daca as scrie produsul A*B ca inmultire intre descompunerile lor, as observa ca toti termenii existenti sunt fie parte a CMMDC, fie parte a CMMMC. De aici apare si relatia A*B=CMMDC(A,B)*CMMMC(A,B). Practic ne vom folosi de CMMMC(A,B)=A*B/CMMDC(A,B).

citeste A,B

A2=A; B2=B; //salvez separat datele initiale

//calculez CMMDC

cat timp (B!=0) {R=A%B; A=B; B=R;}

scrie "CMMDC este ", A2*B2/A.