Código de Pascal/Turbo Pascal - Algoritmo de Euclides

Algoritmo de Euclidesgráfica de visualizaciones


Pascal/Turbo Pascal

estrellaestrellaestrellaestrellaestrella(3)
Publicado el 12 de Febrero del 2006 por Frank Rafael
7.232 visualizaciones desde el 12 de Febrero del 2006. Una media de 14 por semana
Programa que calcula el mcd de dos números enteros mediante el algoritmo de Euclides.
Creado con TP 7.0

Versión 1
estrellaestrellaestrellaestrellaestrella(3)

Publicado el 12 de Febrero del 2006gráfica de visualizaciones de la versión: Versión 1
7.233 visualizaciones desde el 12 de Febrero del 2006. Una media de 14 por semana
estrellaestrellaestrellaestrellaestrella
estrellaestrellaestrellaestrella
estrellaestrellaestrella
estrellaestrella
estrella

Si alguno de los archivos de descarga no funciona, comentanos aquí el error.




Comentarios sobre la versión: Versión 1 (3)

Felman
17 de Febrero del 2006
estrellaestrellaestrellaestrellaestrella
Muy buena implementacion del algoritmo.
Y como siempre Yeah!!. You Got It !!
Responder
Frank Rafael
27 de Febrero del 2006
estrellaestrellaestrellaestrellaestrella
Otras formas de programar el algoritmo.

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

Responder
frank
17 de Septiembre del 2012
estrellaestrellaestrellaestrellaestrella
gracias, me ha servido de mucho.......
Responder

Comentar la versión: Versión 1

Nombre
Correo (no se visualiza en la web)
Valoración
Comentarios

http://lwp-l.com/s1318