Tabla de contenido
8
Programas de Aritmetica
8.1 EL MCD y el Algoritmo de Euclides
Calcular el MCD de dos números enteros positivos A y B.
El algoritmo de Euclides se basa en la definición recursiva de MCD.
MCD(A,0) = A
MCD(A,B) = MCD(B,A mod B) siB
donde A mod B representa el resto de la división euclidiana de A entre B.
Descripción del algoritmo:
Se efectúan las divisiones euclidianas sucesivas:
A = B
Q1+ R1
0
´
B = R1
Q2 + R2 0
´
R1= R2
Q3+ 3
0
´
Después de un número determinado de pasos existe un entero n tal que: R
Entonces obtenemos:
MCDA,B) = MCD(B, R1) = ...
MCD(R
, R
) = MCD(R
n – 1
n
8.1.1
Traduccion en los Calculos Algoritmicos
Versión iterativa
Si B
0 se calcula R = A mod B, B con el valor de A (introduciendo B en A) y
¹
R con el valor de B (introduciendo R en B), así se vuelve a empezar hasta que
B = 0, el MCD es entonces A.
Función MCD(A,B)
Local R
mientras que B
0 ejecutar
¹
A mod B -
R
>
B -
A
>
R -
B
>
/fmientras que/
Programas de Aritmetica
Calculo Simbólico y Matemático con la HP 40G
0
¹
...R1
B
£
<
R2
R1
£
<
R3
R2
£
<
,0) = R
n – 1
n – 1
n
= 0.
141
Tabla de contenido
