martes, 18 de mayo de 2010

Algoritmo Euclidiano (Puntos extra)

Hola profesora y compañeros, aqui les muestro un tema que me llamo la atencion para puntos extra se trata sobre el algoritmo euclidiano.


Algoritmo Euclidiano

Este algoritmo es un método para encontrar el máximo factor común de dos enteros. Primero se divide el número mayor entre el número menor.
Se repite la división, utilizando el residuo como divisor, hasta que el residuo se convierte en cero. El último residuo diferente a cero es el máximo factor común de los dos enteros.

Por ejemplo, para encontrar los máximos factores comunes de 99 y 44, dividimos 44 entre 99. Esto da 2 con un residuo de 11. A continuación, se divide 11 entre 99, que da 9 con un residuo de 0. Ya que 11 es el último residuo diferente a cero, es el máximo factor común de 99 y 44.

Otro ejemplo seria el siguiente
Por ejemplo, para encontrar el máximo común divisor de 93164 y 5826 el algoritmo genera la siguiente secuencia de divisiones:

Paso Operación Significado
1 93164 dividido entre 5826 es 15 y sobran 5774
2 5826 dividido entre 5774 es 1 y sobran 5
3 5774 dividido entre 52 es 111 y sobran 2
4 52 dividido entre 2 es 26 y sobra 0






Su complejidad computacional seria O(log n) divisiones para que se calcule el maximo comun divisor de n y m donde
n>m
Su implementacion en pseudocodigo seria:

Algoritmo en forma recurrente
Funcion
mcd (a,b)
Si b=0 entonces:
El resultado es a
En otro caso:
El resultado es mcd (b, a mod b)

Algoritmo en forma iterativa

Funcion
mcd(a,b):
mientras haga lo siguiente:
El resultado es a
Cualquier duda o sugerencia favor de dejar un comentario.
Gracias

No hay comentarios:

Publicar un comentario