Ejempo del Algoritmo Extendido de Euclides

Si tenemos una ecuación diofántica de primer grado tal que su expresión es de la forma a*x + b*y = MCD  (a,b) el Algoritmo Extendido nos permite calcular los valores de las incognitas x e y. A coantinuación se presenta dicho algoritmo en PseInt:

Proceso AlgoritmoExtendidoEuclides
Definir a como entero;
Definir b como entero;
Definir x como entero;
Definir y como entero;
Definir ux Como Entero;;
Definir uy como entero;
Definir cociente como entero;
Definir tmp como entero;
Definir tmpa como entero;
Definir tmpb como entero;
Definir continuar como Logico;
Definir expresion como cadena;

Escribir "De la expresion a*x + b*c = MCD (a,b)";
Escribir "Ingrese a:";
Leer a;

Escribir "Ingrese b:";
Leer b;

tmpa <-a;
tmpb <-b;

x <- 0;
ux <- 1;
y <- 1;
uy <- 0;

continuar <- verdadero;

Mientras continuar Hacer
cociente <- TRUNC (a/b);
tmp <- a;
a <- b;
b <- tmp % b;
tmp <- x;
x <- ux - cociente*x;
ux <- tmp;
tmp <- y;
y <- uy - cociente*y;
uy <- tmp;
Si b = 0 Entonces
continuar <- falso;
FinSi
FinMientras

Escribir ux,"x",tmpa,"+",uy,"x",tmpb,"=",a;


FinProceso

Basado en Wikipedia

Ejemplo de Algoritmo alternativo al de Euclides que calcula el MCD con operaciones binarias

El algoritmo de Euclides permite el calculo del Máximo Común Divisor. Sin embargo, este requiere de que la realización de divisiones, por eso existe el siguiente algoritmo que permite tal calculo sin que se tenga que efectuar tal operación.


Proceso AlgoritmoEuclidesBinario

 Definir u como entero;
 Definir v como entero;
 Definir desplazamiento Como Entero;
    Definir continuar como logico;
 Definir temporal como entero;
 Definir MCD como entero;

 Escribir "Ingrese uno de los numeros de los que calculara el MCD: ";
 Leer u;

 Escribir "Ingrese uno de los numeros de los que calculara el MCD: ";
 Leer v;

 desplazamiento <- 1;



 Mientras ((u %2 = 0) & (v % 2 = 0)) Hacer

  u <- u /2;
  v <- v /2;
  desplazamiento <- desplazamiento*2;

 FinMientras

 continuar <- verdadero;

 Mientras u % 2 = 0 Hacer
u <- u / 2;
 FinMientras


 Mientras continuar Hacer

  Mientras v % 2 = 0 Hacer
   v <- v / 2;
  FinMientras
  Si u > v Entonces
   temporal <- u;
   u <- v;
   v <- temporal;
  FinSi
  v <- v - u;
  Si v = 0 Entonces
   continuar <- falso;
  FinSi
 FinMientras

    MCD <- desplazamiento*u;
 Escribir "El MCD es :",MCD;


FinProceso

Basado en la Wikipeda