RSS

L11. Cmmdc. Cmmmc

28 Sep

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.

 

OBS. M-am gandit de multe ori cum sa explic elevilor ce anume l-a facut pe Euclid sa se gandeasca la problema cmmdc si mi-am imaginat urmatorul scenariu: Euclid avea o camera de latime A si lungime B pe care sotia lui vroia sa o acopere cu placi patrate de gresie. Pentru a-si impresiona prietenele, placile trebuiau sa acopere integral suprafata camerei si sa fi cat mai mari. Cum a rezolvat Euclid problema? Practic trebuie desenat un caroiaj cu patrate de latura CMMDC.

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;}

//se iese cand B este nul=>

scrie A;

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;}

//afisez CMMMC

scrie “CMMMC este “, A2*B2/A.

 
12 Comments

Posted by on 28/09/2012 in C2_1. Algoritmica

 

Tags: ,

12 responses to “L11. Cmmdc. Cmmmc

  1. Klaudia Emy

    08/05/2013 at 14:37

    pentru codul de la CMMMC ultima linie, nu ar trebui sa fie:

    scrie “CMMMC este”, A2*B2/B

    pentru ca B este CMMDC ( A, B ) conform variantei 5 de CMMDC.

     
  2. mchelariu71

    08/05/2013 at 18:26

    aveam 2 greseli.
    1. la varianta 5 se iese din ciclul cand B este nul, ceea ce inseamna ca cmmdc-ul se gaseste in A
    =>
    2. la CMMMC raspunsul este a2* b2 / a
    Multumesc.

     
  3. oana

    18/02/2014 at 11:50

    La varianta 3. (A-B,B)daca A>B
    (A,B-A)dacaB>A
    A daca A==B
    In algoritm Este folosit : daca A>B atunci A=A-B altfel B=B-A
    cred ca le-ati inversat.🙂 Sau nu reusesc eu sa inteleg logica

     
  4. mchelariu71

    18/02/2014 at 21:12

    scrie un paragraf mai sus:
    “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
    “.
    are logica!🙂

     
  5. oana

    24/02/2014 at 16:22

    Am inteles acum!!🙂

     
  6. Timeea

    26/05/2014 at 15:34

    Doamne,cat mi-as dori sa va am prof…Mda,sunt in clasa a ix-a si informatica mea e pulbere.

     
  7. Marco

    17/07/2014 at 14:04

    Sincer pentru CMMDC cel mai simplu mi se pare algoritmul lui Euclid , pus intr-o functie de verificare nu te complici cu o multime de variabile

     
  8. mchelariu71

    17/07/2014 at 14:12

    Da. algoritmul lui Euclid e clar dar nu e optim. in conditii de examen sau pentru vre-un produs informatic va trebui neaparat sa pui problema optimizarii, a reducerii timpului de executie. Vrei un GPS care sa te lase in asteptare?

     
  9. Cosmin

    12/05/2015 at 21:34

    Pentru mai multe numere cum se face cmmmc?

     
  10. mchelariu71

    13/05/2015 at 11:23

    pentru N numere
    cin > > n;
    cin > > a; // primul numar din sir
    for(i=2; i > n; i + +)
    {
    cin > > b ;
    a = cmmdc( a, b);
    }

    cout<<a;

    WordPress mai modifica textul. adapteaza.

     
  11. Radu

    29/10/2015 at 19:29

    Cum se face cmmdc pentru n numere?

     
  12. mchelariu71

    30/10/2015 at 09:25

    facem cmmdc intre valoarea curenta si urmatorul numar din sir

    cin>> n>> a ; //n si prima valoare din sir
    For(i=2 ;i< = n; i + +) {cin >> b; a=cmmdc(a,b);}
    cout<<a;

     

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: