domingo, 30 de mayo de 2010

Puntos Extras... Algoritmo Euclidiano

<>

Definicion:

Pues principalmente el algoritmo de Euclides es un método simple y eficaz para encontrar el máximo común divisor entre dos números enteros diferentes de cero. Este algoritmo no requiere factorización.

El MCD de dos números enteros es el mayor entero que divide a ambos, mientras que el resto, el algoritmo de Euclides se basa en el principio de que el MDC no cambia si el menor número se resta de la más grande.


Ejemplo Paso a Paso:

Encontrar el MCD de 252 y 105:




OBTENEMOS COMO RESULTADO 21.

Animacion del algoritmo:




Otro ejemplo para que quede mucho mejor explicado:

Calcularemos el MCD de 348 y 156:

348

156

-312


36 ≠ 0

2

¿De qué otra no es cero, reemplazamos el dividendo y el divisor:

156

36



-144


12 ≠ 0

4

¿De qué otra no es cero, reemplazamos el dividendo y el divisor:



36

12

-36


0

3



Así que el máximo común divisor de los 348 enteros y 156 es 12.

cociente

2

4

3

348

156

36

12

resto

36

12

0








TEOREMA DEL ALGORITMO:




Bibliografia:

http://es.wikipedia.org/wiki/M%C3%A1ximo_com%C3%BAn_divisor


http://www.unalmed.edu.co/~earamosn/cursos/matematicas_discretas_09II/plan/notas-AlgNum.pdf


http://pt.wikipedia.org/wiki/Algoritmo_de_Euclides





2 comentarios:

  1. que facil esta este tema... lastima que lo haya entendido un poco tarde :(
    me gusto mucho la animacion que pusiste, explica muy bien el tema (Y)

    ResponderEliminar
  2. Muy clara la explicacion muy sencillo el algoritmo basicamente solo vas remplazando el divisor por el residuo de la division anterior hasta llegar a 0 obteniendo asi el MCD.

    ResponderEliminar