cmmdc divide et impera

Sa se calculeze cmmdc pentru n numere utilizand metoda divide et impera

cmmdc

#include<iostream.h>
int cmmdc(int a[20], int li, int ls)
{ if(li==ls) return a[li];
  else
  { int x,y;
    x=cmmdc(a,li,(li+ls)/2);
    y=cmmdc(a,(li+ls)/2+1,ls);
    while(x!=y)
       if(x>y) x=x-y;
       else y=y-x;
    return x;  
  }   
}
void main()
{
int a[20],n,i;
cout<<“n=”;cin>>n;
for(i=1;i<=n;i++) cin>>a[i];
cout<<“cmmdc este: “<<cmmdc(a,1,n);
}

functie cmmdc

Să se determine cel mai mare divizor comun (c.m.m.d.c.)a doua numere întregi citite de la tastatura.

Cmmdc se va calcula folosind relatia:

cmmdc(a,b)=cmmdc(a-b, b), a>b
=cmmdc(a, b-a), b>a
=a, daca a=b,

#include<iostream.h>
int cmmdc(int a,int b)
{
if(a==b) return a;
else if(a>b) return cmmdc(a-b,b);
else return cmmdc(a,b-a);
}
void main()
{
int x,y;
cout<<“x=”;cin>>x;
cout<<“y=”;cin>>y;
cout<<“cmmdc este: “<<cmmdc(x,y);
}

subprogram cmmdc cmmmc

Sa se scrie cate o functie care sa determine:
– cel mai mare divizor comun a doua numere intregi date ca parametri.
– cel mai mic multiplu comun a doua numere intregi date ca parametri
Indicatii:
– Pentru determinarea cmmdc se va folosi algoritmul lui Euclid prin impartiri
repetate.
– Pentru determinarea cmmmc se va folosi relatia dintre cmmmc si cmmdc: cmmmc(a,b)=(a*b)/cmmdc(a,b)

#include <iostream.h>
int cmmdc(int a, int b)
{
int r;
r=a%b;
while(r!=0)
{
a=b;
b=r;
r=a%b;
}
return b;
}
int cmmmc(int a, int b)
{
return(a*b/cmmdc(a,b));
}
void main(void)
{
int x,y,d,m;
cout<<“Dati primul numar “;cin>>x;
cout<<“Dati al doilea numar “;cin>>y;
d=cmmdc(x,y);
cout<<“C.m.m.d.c este “<<d<<endl;
m=cmmmc(x,y);
cout<<“C.m.m.m.c este “<<m<<endl;
}

{module orizontal600}

cmmdc recursiv

Sa se afle cmmdc pentru 2 numere utilizand varianta recursiva

#include<iostream.h>
int a,b;

int cmmdc(int a,int b)
{
if(a==b) return a;
else
if (a>b) return cmmdc(a-b,b);
else return cmmdc(a,b-a);
}

void main()
{
cout<<“a=”;cin>>a;
cout<<“b=”;cin>>b;
cout<<“cmmdc: “<<cmmdc(a,b);
}

{module orizontal600}

cmmdc

CEL MAI MARE DIVIZOR COMUN – ALGORITMUL LUI EUCLID (metoda impartirilor succesive)

#include<iostream.h>
void main()
{
int a,b,r;
cout<<“a=”;cin>>a;
cout<<“b=”;cin>>b;
r=a%b;
while(r)
{
a=b;
b=r;
r=a%b;
}
cout<<“cmmdc: “<<b;
}

CEL MAI MARE DIVIZOR COMUN – ALGORITMUL LUI NICOMAHUS (metoda scaderilor repetate)

#include<iostream.h>
void main()
{
int a,b,r;
cout<<“a=”;cin>>a;
cout<<“b=”;cin>>b;
while(a!=b)
if(a>b) a=a-b;
else b=b-a;
cout<<“cmmdc: “<<b;
}

{joscommentenable}