Algoritmo de euclides: mcd ...

Solo disponible en BuenasTareas
  • Páginas : 2 (251 palabras )
  • Descarga(s) : 0
  • Publicado : 6 de diciembre de 2011
Leer documento completo
Vista previa del texto
Algoritmo de Euclides: MCD y MCM
Última actualización el Sábado, 18 de Septiembre de 2010 13:28
El algoritmo de Euclides sirve paraobtener el máximo común divisor de dos números enteros positivos.
Se llama así por Euclides de Alejandría , un matemático griego que vivió en lostiempos del faraón Ptolomeo I, del que nos han quedado algunos textos recopilatorios del saber matemático y geométrico de su época.
Es uno delos algoritmos típicos que los profesores de programación ponen a sus alumnos para practicar el bucle repetir-mientras pasando valores de unaiteración a otra del bucle.

El máximo común divisor de dos números enteros positivos a y b es otro número entero positivo c tal que sidividimos a/c y b/c, los restos de las divisiones son 0, y además no existe otro número mayor que c que tenga esta característica.
El algoritmode Euclides es el siguiente.
Algoritmo de Euclides Siendo a y b dos enteros positivos tales que a>b, comenzamos dividiendo a/b, con lo queobtendremos un resto r1 y un cociente q1
a=q1·b+r1
A partir de aquí, repetimos el siguiente proceso:
* dividir el dividendo del pasoanterior entre el resto del paso anterior
* despreciar el cociente
* si el resto es 0, el mcd es el divisor de esta operación, es decir,el último resto no nulo (recordemos que el divisor de esta operación fue el resto en la anterior.
* Si el resto no es 0, ir al primer paso
tracking img