Implementación de algoritmos de teoría de números/Algoritmo de Euclides

De Wikilibros, la colección de libros de texto de contenido libre.

El algoritmo de Euclides es un método antiguo y eficaz para calcular el máximo común divisor (mcd) entre dos números enteros. Fue originalmente descrito por Euclides en la proposición 2 del libro VII de Elementos de Euclides.

Descripción formal[editar]

Versión recursiva[editar]

Utilizando recursión, se puede expresar el algoritmo de manera natural:

 función 
   si  
     devolver 
   si no
     devolver 

Versión iterativa[editar]

La versión iterativa es más eficiente para la implementación en una computadora:

función 
  mientras  hacer
    
    
    
  devolver 

Versión original[editar]

El algoritmo original descrito por Euclides trataba el problema de manera geométrica; usaba la substracción repetida en lugar del residuo de la división. Esta versión es significativamente menos eficiente:

 función 
   mientras  hacer
     si 
       
     si no
       
   devolver 

Implementación en distintos lenguajes de programación[editar]

En lenguaje C[editar]

(versión recursiva)

 unsigned int mcd(unsigned int a, unsigned int b){
     return (b == 0)? a : mcd(b, a % b);
 }

(versión iterativa)

 unsigned int mcd(unsigned int a, unsigned int b){
     unsigned int t;
     while (a > 0){
         t = a;
         a = b % a;
         b = t;
     }
     return b;
 }

[editar]

(versión recursiva)

para mcd :a :b
 si :b = 0 [
  devuelve :a
 ] sino [
  devuelve mcd :b resto :a :b
 ]
fin

(versión iterativa)

para mcd :a :b
 mientras [:a > 0] [
  haz "t :a
  haz "a resto :b :a
  haz "b :t
 ]
 devuelve :b
fin

En lenguaje Visual Basic 8[editar]

(versión iterativa)

 Public Function mcd(a As UInteger, b As UInteger) As UInteger
     Dim t As UInteger
     While a > 0
         t = a
         a = b Mod a
         b = t
     End While
     Return b
 End Function

En lenguaje Haskell[editar]

(versión recursiva)

mcd::Int->Int->Int
mcd a 0 = a
mcd a b = mcd b (mod a b)

En lenguaje Pascal[editar]

(versión iterativa)

 function MCD(a , b : integer): integer;
 var
   t:integer;
 begin
     while a > 0 do
     begin
       t := a;
       a := b mod a;
       b := t;
     end;
   result:=b;
 end;

En lenguaje Java[editar]

(versión iterativa)

	public MCD(int a, b,  t) {
	  while(a>0){
	   t=a;
	   a=b%a;
	   b=t;
	  }
	  System.out.println("El maximo comun divisor es: "+b);
 	 }

En lenguaje Python[editar]

(versión recursiva)

def mcd(a, b):
    if b == 0:
        return a
    return mcd(b, a % b)