Algoritmo de Euclides | En C++

El M.C.D.(Máximo Común Divisor) de dos números es aquel entero mayor que los divide a ambos y es utilizado entre otras cosas para simplificar fracciones y obtener el Mínimo común multiplo. El algoritmo de Euclides es un método reiterativo para encontrar de forma rápido el MCD de dos números enteros.

Algoritmo

El algoritmo de Euclides para encontrar MCD(A,B) es como sigue:

  • Si A>B intercambiamos los valores de A y B
  • Si B = 0 entonces MCD(A,B)=A, ya que el MCD(A,0)=B, y podemos detenernos.
  • Escribe A en la forma cociente y residuo (A = B ⋅Q + R).
  • Encuentra MCD(B,R) usando el algoritmo de Euclides ya que MCD(A,B) = MCD(B,R).

En otras palabras, verificamos si A >B,  si lo es intercambiamos los valores de A y B, si A es 0 entonces A es el MCD sino convertimos MCD(A,B)=MCD(B,R) donde R es el residuo(A,B).  Esto es debido a que MCD de dos números también divide al resto obtenido de dividir el mayor entre el más pequeño, por este aspecto B>A y ese es la razón de la primera condición.

El proceso se repite hasta encontrar que A sea 0.

Ejemplo:

Encontral el MCD(160,120)

A=160

B=120

Como (A>B) intercambiamos

A=120

B=160

Inicia Ciclo

MCD(120,160)

Como es B≠0

MCD (160,Resto(160,120)) ⇒ MCD (160,40)

Fin Ciclo

Se reite el ciclo para MCD (160,40)

Lo cual da arroja que el Resto entre 160 y 40 es cero, por lo que el MCD es 40

El código en C++

Vamos a utilizar una función recursiva(que se llama a sí misma) que nos permita obtener el valor con menos código y por ende más rapido.

inline int MCD(int a, int b) {
	
if (b==0) return a;
    else return MCD(b,b%a); 
}

Igualmente se necesita una función para intercambio de A y B si A>B

void intercambiar(int &a,int &b){
    int aux=a;
    a=b;
    b=aux;
    }

Y otra función que evalue si A>B llamando a la función intercambiar y luego a la imprimiendo el valor de la función MCD

inline void algEuclides(int a, int b){
    
    if(a>b)
        intercambiar(a,b);    
    cout << "MCD(" << a << ","<<b<<")=" <<MCD(a,b)<<endl;
    }

en la función main() llamamos a la función algEuclides

algEuclides(atoi(argv[1]),atoi(argv[2]));

Como los valores de A y B lo vamos a recibir desde la línea de comando vamos utilizamos una función atoi() de la biblioteca stdlib.h que convierta los valores de char * a int.

Aquí el código completo:

//Calculo de minimo comun divisor entre dos numeros
#include <iostream>
#include <stdlib.h>
using namespace std;
 
inline int MCD(int a, int b) {    
if (b==0) return a;
    else return MCD(b,b%a);  
}
void intercambiar(int &a,int &b){
    int aux=a;
    a=b;
    b=aux;
    }
inline void algEuclides(int a, int b){
    
    if(a>b)
        intercambiar(a,b);    
    cout << "MCD(" << a << ","<<b<<")=" <<MCD(a,b)<<endl;
    }
int main(int argc, char **argv)
{       
         algEuclides(atoi(argv[1]),atoi(argv[2]));
         return 0;
}

Para ejecutar nuestro programa en la línea de comando ejecutamos

Si el nombre del código fuente es MCD.cpp:

./CMD 120 160

En windows

CMD.exe 120 160

El resultado es lo siguiente:

Algoritmo de Euclides

Fuentes:

https://es.wikipedia.org/wiki/M%C3%A1ximo_com%C3%BAn_divisor#Aplicaciones

https://es.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/the-euclidean-algorithm

Guardar

2 opiniones en “Algoritmo de Euclides | En C++”

  1. Pequeña inversión de letras …
    Si el nombre del código fuente es MCD.cpp
    se debería leer:
    “./MCD 120 160” – Linux
    “MCD.exe 120 160” – Windows

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *