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

Versión 1
estrellaestrellaestrellaestrellaestrella(3)

Publicado el 12 de Febrero del 2006gráfica de visualizaciones de la versión: Versión 1
10.898 visualizaciones desde el 12 de Febrero del 2006
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)

17 de Febrero del 2006
estrellaestrellaestrellaestrellaestrella
Muy buena implementacion del algoritmo.
Y como siempre Yeah!!. You Got It !!
Responder
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
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...
CerrarCerrar
CerrarCerrar
Cerrar

Tienes que ser un usuario registrado para poder insertar imágenes, archivos y/o videos.

Puedes registrarte o validarte desde aquí.

Codigo
Negrita
Subrayado
Tachado
Cursiva
Insertar enlace
Imagen externa
Emoticon
Tabular
Centrar
Titulo
Linea
Disminuir
Aumentar
Vista preliminar
sonreir
dientes
lengua
guiño
enfadado
confundido
llorar
avergonzado
sorprendido
triste
sol
estrella
jarra
camara
taza de cafe
email
beso
bombilla
amor
mal
bien
Es necesario revisar y aceptar las políticas de privacidad

http://lwp-l.com/s1318