Archive
Archive for February 27th, 2008
Problema 1
Empiezo aquà una serie de artÃculos de periodicidad variable que lo único que pretende es ser algo similar (de una manera muy amplia) a PyEuler. La lista completa de problemas está en el Proyecto Euler y, como no podÃa ser de otra manera, empiezo por el primero.
Enunciado:
Halla la suma de todos los números menores que 1000 y múltiplos de 3 o de 5.
Solución 1:
RUBY:
-
def euler1a(e, numbers)
-
(1..e).select{|x| numbers.any?{|y| (x%y == 0)}}.inject{|memo,o| memo+=o}
-
end
-
-
puts euler1a(1000,[3,5])
La explicación es simple. Tenemos un rango desde 1 hasta el lÃmite, filtramos los que son múltiplos de algún elemento del array y después se suman.
Solución 2:
RUBY:
-
def euler1b(e,numbers)
-
(1..e).inject(0){|memo,o| (numbers.any?{|x| (o%x)==0}) ? memo+o : memo }
-
end
-
-
puts euler1b(1000,[3,5])
Éste es similar al anterior, sólo que se suma según se recorre el rango.
Solución 3:
Para este necesitamos antes un par de funciones. La primera, halla el máximo común divisor de dos números. Para ello, básicamente usa el algoritmo de Euclides.
RUBY:
-
def mcd(n1,n2)
-
if n1 <n2
-
mcd(n2,n1)
-
elsif (n1%n2) == 0
-
n2
-
else
-
mcd(n2,n1%n2)
-
end
-
end
Por otra parte, está la función que calcula el mÃnimo común múltiplo. Para ello usa su relación con el m.c.d..
RUBY:
-
def mcm(n1,n2)
-
n1*n2/mcd(n1,n2)
-
end
Con esto, ya podemos pasar a la tercera solución, que es diferente de las otras dos en que sólo sirve si utilizamos dos números como filtro.
RUBY:
-
def euler1c(limit, n1, n2)
-
(n1*((limit/n1)*((limit/n1)+1)/2)+n2*((limit/n2)*((limit/n2)+1)/2)-mcm(n1,n2)*((limit/mcm(n1,n2))*((limit/mcm(n1,n2))+1)/2))
-
end
-
-
puts euler1c(1000,3,5)
La explicación es un poco más complicada, pues implica teorÃa básica de conjuntos y la conocida fórmula de la suma de 1 a n.
Ahora es vuestro turno. ¿Cómo se os ocurre hacerlo?
Improve the web with Nofollow Reciprocity.
Mi Wishlist
