Algoritmos
Páginas: 3 (702 palabras)
Publicado: 23 de septiembre de 2011
ALGORITMO DE EUCLIDES
El máximo común divisor de dos enteros puede obtenerse escogiendo el mayor de todos los divisores comunes. Hay un proceso más eficiente que utiliza repetidamente el algoritmode la división. Este método se llama algoritmo de Euclides.
El algoritmo de Euclides se describe de la forma siguiente:
Dados dos enteros a y b cuyo máximo común divisor se desea hallar, yasumiendo que a b > 0, (El método funciona también si a y b son negativos). Basta trabajar con los valores absolutos de estos números, debido a que M.C.D (|a|, |b|) =M.C.D (a,b) se siguen los siguientespasos:
a) Se usa el algoritmo de la división para obtener a = q1b + r2 con
0 £ r1 < b. Si r1 = 0, entonces bïa y M.C.D.(a, b) = b.
b) Si r1 ¹ 0 se divide b por r1 y se producen enteros q2y r2 quesatisfacen b =q2 r1 + r2 con 0 £ r2 < r1. Si r2 = 0 el proceso termina y M.C.D.(a, b) = r1.
c) Si r2 ¹ 0 se procede a dividir r2 por r1 obteniendo r1 = q3 r2 + r3 con 0 £ r3 < r2.
d) Esteproceso continua hasta que algún residuo cero aparece. Esto ocurre porque en la secuencia b > r1 > r2 > ..... ³ 0 no puede haber más de b enteros. Es decir, el proceso es finito.
e) En estascircunstancias, el máximo común divisor de a y b no es más que el último residuo no cero del proceso anterior.
Esto lo garantiza la aplicación reiterada del siguiente teorema.
Teorema. Si a y b son enterospositivos con a ³ b y si a = qb + r entonces M.C.D.(a, b) = M.C.D.( b, r ).
ALGORITMOS RECURSIVOS
Un algoritmo se dice que es recursivo cuando tiene la capacidad de llamarse o invocarse a símismo o de llamar a otro algoritmo desde el cual se puede volver a invocar al primero. En cualquier caso, se garantiza que el número de llamadas recursivas que se realizan es finito (es decir, en algúnmomento DEBE finalizar la ejecución del algoritmo). Para ello, cada llamada recursiva resuelve un problema de menor tamaño, uno tras otro, hasta llegar a un problema cuya resolución sea directa o...
El máximo común divisor de dos enteros puede obtenerse escogiendo el mayor de todos los divisores comunes. Hay un proceso más eficiente que utiliza repetidamente el algoritmode la división. Este método se llama algoritmo de Euclides.
El algoritmo de Euclides se describe de la forma siguiente:
Dados dos enteros a y b cuyo máximo común divisor se desea hallar, yasumiendo que a b > 0, (El método funciona también si a y b son negativos). Basta trabajar con los valores absolutos de estos números, debido a que M.C.D (|a|, |b|) =M.C.D (a,b) se siguen los siguientespasos:
a) Se usa el algoritmo de la división para obtener a = q1b + r2 con
0 £ r1 < b. Si r1 = 0, entonces bïa y M.C.D.(a, b) = b.
b) Si r1 ¹ 0 se divide b por r1 y se producen enteros q2y r2 quesatisfacen b =q2 r1 + r2 con 0 £ r2 < r1. Si r2 = 0 el proceso termina y M.C.D.(a, b) = r1.
c) Si r2 ¹ 0 se procede a dividir r2 por r1 obteniendo r1 = q3 r2 + r3 con 0 £ r3 < r2.
d) Esteproceso continua hasta que algún residuo cero aparece. Esto ocurre porque en la secuencia b > r1 > r2 > ..... ³ 0 no puede haber más de b enteros. Es decir, el proceso es finito.
e) En estascircunstancias, el máximo común divisor de a y b no es más que el último residuo no cero del proceso anterior.
Esto lo garantiza la aplicación reiterada del siguiente teorema.
Teorema. Si a y b son enterospositivos con a ³ b y si a = qb + r entonces M.C.D.(a, b) = M.C.D.( b, r ).
ALGORITMOS RECURSIVOS
Un algoritmo se dice que es recursivo cuando tiene la capacidad de llamarse o invocarse a símismo o de llamar a otro algoritmo desde el cual se puede volver a invocar al primero. En cualquier caso, se garantiza que el número de llamadas recursivas que se realizan es finito (es decir, en algúnmomento DEBE finalizar la ejecución del algoritmo). Para ello, cada llamada recursiva resuelve un problema de menor tamaño, uno tras otro, hasta llegar a un problema cuya resolución sea directa o...
Leer documento completo
Regístrate para leer el documento completo.