Ir al contenido

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 recursiva)

Public Shared Function mcd(ByVal a As Integer, ByVal b As Integer) As Integer
	If b = 0 Then
		Return a
	Else
		Return mcd(b, a Mod b)
	End If
End Function

(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)

(versión iterativa)

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