
Algoritmo de Euclides
Pascal/Turbo Pascal
Publicado el 12 de Febrero del 2006 por Frank Rafael (19 códigos)
11.037 visualizaciones desde el 12 de Febrero del 2006
Programa que calcula el mcd de dos números enteros mediante el algoritmo de Euclides.
Creado con TP 7.0
Creado con TP 7.0
Comentarios sobre la versión: Versión 1 (3)
Y como siempre Yeah!!. You Got It !!
El algoritmo de Euclides, para calcular el máximo común divisor está basado en lo siguiente:
Teorema:
========
Para cualquier entero no negativo a y cualquier positivo b gcd(a,b) = gcd(b, a mod b)
A continuación un algoritmo recursivo basado en el teorema. Pueden hacerse versiones más eficientes de forma iterativa.
EUCLID (a,b)
1 if b = 0
2 then return a
3 else return EUCLID(b, a mod b)
La forma extendida del algoritmo de Euclides
====================================
El algoritmo de Euclides puede extenderse para calcular información útil. Específicamente para calcular los coeficientes enteros x e y tal que:
d = gcd(a,b) = ax + by
Note que x e y pueden ser 0 o negativos. Estos coeficientes serán usados por próximos algoritmos.
EXTENDED-EUCLID(a, b)
1 if b = 0
2 then return (a, 1, 0)
3 (d',x',y') = EXTENDED-EUCLID(b, a mod b)
4 (d,x,y) = (d',y' ,x' - a/b y')
5 return (d,x,y)
Este procedimiento es una variación del algoritmo de Euclides.
==================================================
Tenemos que:
d = gcd(a,b) = d’ = gcd(b, a mod b)
d = ax+by = d’ = bx’ + (a mod b)y’
= bx’+ (a-[a/b]b)y’
= bx’ + ay’ – [a/b]by’
= ay’ + b(x’-[a/b]y’)
de donde x =y’ y = x’ –[a/b]y’
Notas:
=====
Tomado de:
Algoritmos
Nociones elementales en la teoría de los números
Tema por:
Ronny López Trujillo
Selección Nacional de Cuba
XIV IOI Yong-In Korea 2002