Problem
Donald Knuth, autor de “
The Art of Programming”, considera que el algoritmo de Euclides es el primero de la historia. Porque, a pesar de que el algoritmo fue inventado y utilizado incluso antes de
Euclid, que vivió en los siglos IV-III. antes de Cristo (ya lo menciona
Aristóteles, que vivió un siglo antes), Euclides describe iterativamente el proceso, que es consistente con el significado moderno de la palabra "algoritmo".
"Reemplaza el mayor de los dos números con la diferencia entre el mayor y el menor hasta que sean iguales. Esto es GCD."
El algoritmo de Euclides en sí mismo es familiar para cualquier escolar moderno. La descripción matemática se puede ver
aquí. Implementar
clásico Algoritmo de Euclides y formatéelo como una función
nod(a, b) que toma 2 números como entrada y devuelve el máximo común divisor de estos dos números.
¡No se requiere entrada ni salida! Solo necesita implementar la función.
Запрещенные операторы: gcd;%