Etichete : cel mai mare divizor comun, cel mai mic multiplu comun, cmmdc, cmmmc

In urmatoarea perioada voi propune si voi rezolva probleme simple pentru un incepator in algoritmica si C/C++ pentru a incerca sa aducem si sa trezim interesele si celor mai slabuti dintre noi.

In general pentru calcularea celui mai mare divizor comun se foloseste algoritmul algoritmul lui Euclid prin scaderi repetate sau prin impartiri repetate.De preferat pentru timpul de executie este calcularea celui mai mare divizor comun prin impartiri repetate.

Calcularea celui mai mare divizor comun (CMMDC) prin scaderi repetate

#include <stdio.h>
int main()
{
	int a,b;
	scanf("%d %d",&a,&b);
	while(a!=b)
	{
		if(a>b)
			a=a-b;
		else
			b=b-a;
	}
	printf("cmmdc= %d",a);
	return 0;
}

Calcularea celui mai mare divizor comun (CMMDC) prin impartiri repetate

#include <stdio.h>
int main()
{
	int a,b,r;
	scanf("%d %d",&a,&b);
	r = a % b;
        while(r != 0)
        {
           a = b;
           b = r;
           r = a % b;
        }

	printf("cmmdc= %d",b);
	return 0;
} 

O varianta recursiva pentru cel de-al doilea algoritm si mult mai simplu de memeorat:

int cmmdc(int a, int b)
{
    if((!a) || (!b)) return a+b;
    if(a>b) return cmmdc(a%b,b);
    return cmmdc(a,b%a);
}

Calcularea celui mai mic multiplu comun(CMMMC)

Ne putem folosi de formula CMMMC = a*b/CMMDC.

#include <stdio.h>
int main()
{
	int a,b,r,c,x,y;
	scanf("%d %d",&a,&b);
	x=a;
	y=b;
	while(b!=0)
	{
		r=a % b;
		a=b;
		b=r;
	}
	printf("cmmdc= %d\n",a);
	c=x*y/a;
	printf("cmmmc= %d",c);
	return 0;
}

Recomandam, pe aceeasi tema

Despre autorul articolului :

Avădănei Andrei - Autorul a scris 591 articole (vezi lista completa).

Contact | andrei@worldit.info | @worldIT – @AndreiAvadanei

Fondator si redactor worldit.info, ma numesc Andrei si sunt pasionat de programare , in special de algoritmica si web development. Forumul WorldIT iti sta la dispozitie daca ai nevoie de suport tehnic, informatii si sugestii privind diverse produse prezentate pe blog si nu numai. Mai multe detalii despre activitatile mele aici.