Saltar al contenido

MCD y Euclides

Lección 2 de 5 · 4 min

MCD y Euclides

Paso 1 de 7

El máximo común divisor (MCD) es la regla más larga que mide ambas longitudes exactamente.

La idea

El máximo común divisor (MCD) es la regla más larga que mide exactamente los dos números.

Coloca la longitud más corta sobre la más larga. Lo que sobresale también tiene que poder medirse con esa regla, así que gcd(a, b) se convierte en gcd(b, a % b). El par se reduce en unas pocas divisiones, y un resto de cero da la respuesta.

Ejemplo del mundo real

Las herramientas de video lo usan para simplificar relaciones de aspecto: 1920 por 1080 tienen un MCD de 120, y así aparece la etiqueta “16:9”. La misma reducción mantiene ordenadas las fracciones en motores de layout y en código de facturación, donde el punto flotante se desviaría.

El código

Te toca

Completa el espacio en blanco.

def gcd(a, b):
    while b:
        a, b = b, ___
    return a

Mini quiz

1 / 3

¿Qué detiene el bucle del algoritmo de Euclides?