Algoritmo de euclides: mcd ...
Páginas: 2 (251 palabras)
Publicado: 6 de diciembre de 2011
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
Ú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
Leer documento completo
Regístrate para leer el documento completo.