Project Euler: Problema 5 con clojure

Vamos con el problema semanal del proyecto euler para practicar con Clojure. Hoy toca el problema 5:

2520 es el menor número divisible entre todos los números del 1 al 10.

¿Cuál es el menor número divisible entre todos los números del 1 al 20?

Tenemos que calcular el mínimo común múltiplo de los números del 1 al 20 y para ello nos vamos a basar en dos propiedades:

  1. mcm(a, b) = a * b / mcd(a, b); donde mcd es el máximo común divisor.
  2. mcm(a, b, c) = mcm(mcm(a, b), c)

Veamos el código poco a poco. Lo primero que necesitamos es poder calcular el máximo común divisor, para lo que podemos usar el algoritmo de Euclides:

(defn mcd [a b] 
  (if (= b 0) a (recur b (mod a b))))

Lo más interesante de esta función es recodar que con recur estamos haciendo una llamada recursiva final, por lo que resulta muy eficiente (prácticamente igual que si fuese un algoritmo iterativo) y no habrá problemas de desbordamiento de pila.

Ahora, podemos calcular el mínimo común múltiplo teniendo en cuenta las dos propiedades anteriores:

(defn mcm
  ([x y] (/ (* x y) (mcd x y)))
  ([x y & xs] (reduce mcm (mcm x y) xs)))

Esto nos permite ver dos cosas interesante. Por una parte podemos definir en clojure funciones que soportan distinto número de parámetros. En este caso, cuando la función recibe dos parámetros aplica la propiedad 1 para calcular el mínimo común múltiplo, y cuando recibe más de 2, aplica la propiedad 2.

Por otra parte, podemos indicar que una función trabaja con un número variable de parámetros (como es el segundo caso de esta función); para ello se usa la sintaxis [x y & xs], es decir, se coloca un & y después una variable que recibirá una lista con el resto de parámetros.

Poniéndolo todo junto podemos resolver ya el problema:

(defn mcd [a b] 
  (if (= b 0) a (recur b (mod a b))))

(defn mcm
  ([x y] (/ (* x y) (mcd x y)))
  ([x y & xs] (reduce mcm (mcm x y) xs)))

(apply mcm (range 1 21))

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos necesarios están marcados *

*

Puedes usar las siguientes etiquetas y atributos HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>