IMPLEMENTACIÓN DEL ALGORITMO DE EUCLIDES EXTENDIDO EN JAVA

El algoritmo de Euclides es un método antiguo y eficaz para calcular el máximo común divisor (MCD). Fue originalmente descrito por Euclides en su obra Elementos. El algoritmo de Euclides extendido es una ligera modificación que permite además expresar al máximo común divisor como una combinación lineal. Este algoritmo tiene aplicaciones en diversas áreas como álgebra, teoría de números y ciencias de la computación entre otras. Con unas ligeras modificaciones suele ser utilizado en computadoras electrónicas debido a su gran eficiencia.

Algoritmo:

Euclides Extendido Versión Interativa:

public class Euclides {
    public long[] euclidesExtendido(long a, long b) 
{
 long[] resp = new long[3];
 long x=0,y=0,d=0;
 if(b==0)
 {
  resp[0] = a; resp[1] = 1; resp[2] = 0;
 } 
 else
 {
  long x2 = 1, x1 = 0, y2 = 0, y1 = 1;
  long q = 0, r = 0;
  while(b>0)
  {
   q = (a/b);
   r = a - q*b;
   x = x2-q*x1;
   y = y2 - q*y1;
   a = b;
   b = r;
   x2 = x1;
   x1 = x;
   y2 = y1;
   y1 = y;
  }
  resp[0] = a;
  resp[1] = x2;
  resp[2] = y2;
    }
 return resp;  
    } 
}

Euclides Extendido Versión Recursiva:

 
//mcd=0,x=0,y=0 en un inicio
public double euclidesExtendidoRe(double a, double b,double mcd,double x, double y)
{     
        double x2=0.0,y2=0.0,x1=0.0,y1=0.0;
        if (b == 0)  {  
            mcd = a;
            x2 = 1;
            y2 = 0;
        }
        else
        {     
            euclidesExtendidoRe (b,a%b,mcd,x,y);
            x1= x2; y1=y2; x2=y1;
            y2=x1- (a/b)*y1;   
        }
        return mcd;
} 

Espero que les sea de utilidad , hasta la siguiente publicación.

• Tweet
• Share
• Share
• Share
• Share