Para este tema, primero debe conocer el máximo divisor común (GCD) y la operación MOD.
Máximo divisor común (GCD)
El MCD de dos o más enteros es el entero más grande que divide cada uno de los enteros de manera que su resto sea cero.
He aquí un ejemplo:
MCD de 20; 30 = 10 (10 es el número más grande que divide a 20 y 30 con el resto de 0)
MCD de 42, 120, 285 = 3 (3 es el número más grande que divide a 42, 120 y 285 con el resto de 0)
Operación "mod"
La operación mod le da el resto cuando se dividen dos enteros positivos. Lo escribimos de la siguiente manera:
A mod B = R
Esto significa que dividir A por B te da el resto R. Esto es diferente a tu operación de división que te da el cociente.
He aquí un ejemplo:
7 mod 2 = 1 (Dividir 7 entre 2 da el resto 1)
42 mod 7 = 0 (Dividiendo 42 entre 7 da el resto 0)
Si comprende los dos conceptos anteriores, comprenderá fácilmente el algoritmo euclidiano.
Algoritmo euclidiano para el máximo divisor común (GCD)
El algoritmo euclidiano encuentra el MCD de 2 números.
Comprenderá mejor este algoritmo viéndolo en acción. Suponiendo que desea calcular el MCD de 1220 y 516, apliquemos el algoritmo euclidiano.
Pseudo código del algoritmo:
Paso 1: Dejado a, bser los dos números
Paso 2: a mod b = R
Paso 3: Deja a = byb = R
Paso 4: repita los pasos 2 y 3 hasta que a mod bsea mayor que 0
Paso 5: MCD = b
Paso 6: Terminar
Aquí está el código Javascript para realizar GCD:
function gcd(a, b) { var R; while ((a % b) > 0) { R = a % b; a = b; b = R; } return b; }Aquí está el código Javascript para realizar GCD usando recursividad:
function gcd(a, b) { if (b == 0) return a; else return gcd(b, (a % b)); }También puede usar el algoritmo euclidiano para encontrar MCD de más de dos números. Dado que GCD es asociativo, la siguiente operación es válida: GCD(a,b,c) == GCD(GCD(a,b), c)
Calcula el MCD de los dos primeros números, luego encuentra el MCD del resultado y el siguiente número. Ejemplo:GCD(203,91,77) == GCD(GCD(203,91),77) == GCD(7, 77) == 7
Puede encontrar GCD de nnúmeros de la misma manera.