Esta es (una versión de) lo que se conoce como el algoritmo euclidiano.
La idea es que, en cada recursión, nos transformemos en un nuevo par de números con los mismos divisores comunes que el par anterior. Hacemos esto hasta que podamos distinguir fácilmente el MCD, y luego terminamos.
Entonces: ¿Por qué (num1, num2) tienen los mismos divisores comunes que (num2, num1% num2)?
- Cómo mostrar que la distancia más corta entre 2 curvas que no se cruzan siempre se encuentra a lo largo de su normal común
- ¿Cómo obtenemos el número total de formas de la disposición de n cosas distintas en n lugares correspondientes donde ningún elemento está colocado correctamente?
- ¿Cuál es el algoritmo de esta pregunta de Hacker-Rank?
- ¿Cuál es tu problema de programación dinámica favorito?
- ¿Cuál es una buena manera de ordenar temas en términos de qué aprender primero para la programación competitiva?
Digamos num3 = num1% num2. Tenga en cuenta que el operador% se define de modo que num3 y num1 difieran en un múltiplo de num2. Es decir, num3 = num1 – k * num2, para algunos k. En consecuencia, si alguien divide num1 y num2, también debe dividir num3. Por el contrario, si alguien divide num2 y num3, también debe dividir num3 + k * num2 = num1. Por lo tanto, vemos que (num1, num2) y (num2, num3) tienen los mismos divisores comunes.
Esto justifica la recursividad. Ahora, ¿qué pasa con el caso base? ¿Por qué gcd (n, 0) = n? Bueno, cada número divide 0, entonces mcd (n, 0) es el máximo divisor de n. Esto será n en sí mismo. [Nota pedagógica: consideramos que mcd (x, y) significa cualquier divisor común de xey que es divisible por todos los demás divisores comunes. Por lo tanto, no es un problema para nosotros que gcd (n, 0) = n incluso cuando n no es positivo]
Finalmente, ¿cuánto tiempo tarda este algoritmo en ejecutarse? Bueno, tenga en cuenta que en cada recursión, la segunda entrada se acerca a cero. Por lo tanto, el algoritmo no puede tomar más de num2 iteraciones para alcanzar su caso base, y luego terminamos.
En realidad, el algoritmo funciona mucho más rápido que eso, pero es un dolor innecesario demostrar que lo hace (cuando se interpreta de la manera habitual). ¡Entonces no voy a hacerlo! En cambio, me apartaré de lo que hacen muchos libros de texto y señalaré que este algoritmo se puede modificar trivialmente para que sea más rápido y que su tiempo de ejecución sea obvio.
En el algoritmo, usaste el operador%. Pero la única propiedad que necesitábamos para justificar la recursión era que x y (x% y) diferían en un múltiplo de y.
De acuerdo con esto, en lugar de utilizar el comportamiento estándar x% y (que, para positivo y, devuelve un valor en algún lugar de 0 a y – 1), voy a proponer un ligero cambio: si x% y normalmente devolvería un valor entre y / 2 e y, reste y de eso y devuelva un valor entre -y / 2 y 0 en su lugar.
Este% operador modificado todavía tiene la propiedad que nos interesa, por lo que funcionará igual de bien para nuestros propósitos. [Si se siente incómodo dejando que las entradas negativas entren, dele un valor absoluto a ellas; no hace ninguna diferencia para nuestras preocupaciones de MCD, ya que los divisores de un número son los mismos que los divisores de su valor absoluto]
Pero ahora tenemos la garantía aún más fuerte de que | num2 | se reducirá en al menos un factor de 2 en cada recursión. Por lo tanto, sabemos que el número de iteraciones para llegar al caso base será como máximo el número de bits en | num2 |. (Básicamente, el logaritmo de base 2 de | num2 |).
[En realidad, podemos dar un análisis más complicado y obtener un límite más estricto en el número de iteraciones de esta versión del algoritmo (podemos mostrar que el número de iteraciones está limitado más precisamente por la base [matemática] (1 + \ sqrt) {2}) [/ math] logaritmo de | num2 | en lugar del logaritmo de base 2), pero no te molestaré con eso por ahora. (Por supuesto, para entradas particulares, tendremos suerte y tomaremos mucho menos tiempo).]
