[C++]Algoritm CMMDC si CMMMC

[~Wolf~]

Algoritm pentru a afla CMMDC(cel mai mare divizor comun) si CMMMC(cel mai mic multiplu comun) al unui numar natural.

Pentru CMMDC:
Varianta 1 - impartiri repetate

#include <iostream>
using namespace std;
unsigned int a,b,r; //declaram numerele (le-am declarat naturale fiindca asa prefer)
int main()
{
cin>>a>>b;
//structura repetitiva se repeta pana cand al doilea numar b va fi egal cu 0, primul numar a va lua valoarea celui de-al doilea numar , iar al doilea numar va lua valoarea restului impartirii dintre a si b
while(b)
{
r=a%b;
a=b;
b=r;
}
cout<<"Cel mai mare divizor comun al celor doua numere este: "<<a; //afisam rezultatul
return 0;
}

Varianta 2 - scaderi repetate , o varianta care dureaza putin mai mult din cauza a prea multor scaderi
#include <iostream>
using namespace std;
unsigned int a,b;
int main()
{
cin>>a>>b;
//parcurgem structura repetitiva pana cand a=b, astfel algoritmul continua cautarea celui mai mare numar si scaderea din acesta, a celui de-al doilea numar
while(a!=b)
{
if(a>b)
a-=b;
else
b-=a;
}
//cum am spus mai sus, algoritmul lucreaza pana cand a=b, asadar putem afisa ori a ori b, la decizia folositorului
cout<<"Cel mai mare divizor comun al celor doua numere este: "<<a;
return 0;
}

BONUS!- Varianta 3 - Varianta recursiva
#include <iostream>
using namespace std;
unsigned int a,b;
unsigned int cmmdc(unsigned int a, unsigned int b) //prototipul functiei
{
if(!b) //conditia de oprire - cand b=0 atunci returnam a care va lua valoarea celui mai mare divizor comun
return a;
return cmmdc(b,a%b); //repetam functia pana gasim rezultatul dorit
}
int main()
{
cin>>a>>b; //citim numerele
cout<<"Cel mai mare divizor comun al celor doua numere este: "<<cmmdc(a,b); //apelam functia
return 0;
}

Personal va recomand prima varianta datorita eficientei din punct de vedere al timpului


Pentru CMMMC:

#include <iostream>
using namespace std;
unsigned int a,b,x,y;
int main()
{
//ne vom folosi de doua variabile pentru a apela la formul aflarii cmmmc cu ajutorul cmmdc
cin>>a>>b;
x=a;
y=b;
//algoritmul cmmdc prin scaderi repetate pe care l-am prezentat si mai sus
while(x!=y)
{
if(x>y)
x=x-y;
else
y=y-x;
}
cout<<"Cel mai mic multiplu comun al celor doua numere este: "<<(a*b)/x; //formula cmmmc cu ajutorul cmmdc
return 0;
}


NOTA!
-desigur ca in locul algoritmului cu scaderi repetate putem folosi algoritmul cu impartirile repetate, ramane la alegerea dumneavoastra
-va rog lasati reply daca gasiti orice fel de greseala, ma ajuta mult