lunes, febrero 08, 2010

Así descubrí el proyecto Euler

Hace unos meses, a los pocos días de que estrenaba yo chamba, hubo necesidad de aprender un nuevo lenguaje de programación. Digo que era nuevo porque yo no lo conocía aunque se trata de un lenguaje más viejo que yo (aquí el link por si alguien tiene curiosidad por saber de qué lenguaje hablo, unas de las características chidas es que los arreglos están guardados en árboles-b y son persistentes).

Por las mismas fechas, en uno de tantos feeds compartidos, leí de un computito ultramarino que recomendaba un sitio para perder el tiempo practicar matemáticas y programación, el Proyecto Euler.

El Proyecto Euler es un conjunto de problemas matemáticos y de computación. Uno se registra y tiene acceso a 277 problemas de complejidad variable. Una manera de darse una idea de si el problema que uno quiere resolver es "complejo" es fijarse en el número de gente que lo ha resuelto. Por ejemplo, el primero ha sido resuelto por 86964 fulanos mientras que los últimos sólo los han resuelto algunas decenas de personas. Una vez que se proporciona la respuesta correcta, el Proyecto Euler le da a uno acceso a un foro donde uno ve la solución de otros participantes lo que siempre es instructivo para llegar a la conclusión: "ay, qué pendejo soy".

Los problemas tienen enunciados precisos. Para qué vean de que hablo voy a echar a perder el primero.

"Si listamos todos los números naturales menores a 10 que sean multiplos de 3 y 5, obtenemos 3, 5, 6, y 9. La suma de estos multiplos es 23.

Encuentra la suma de todos los múltiplos de 3 o 5 menores a 1000."
Con pocas cosas me he topado tan oportunas. Por un lado tenía 277 problemas de matemáticas y computación para resolver y por otro lado, debía aprender un lenguaje de programación nuevo.

Creé un archivo nuevo en Vi y después de consultar un manual para familiarizarme con la sintaxis del lenguaje nuevo me puse a resolver el problema.

La aproximación talachuda de fuerza bruta para resolver el problema que he mencionado (y por la que yo me fuí pues me interesaba aprender a usar iteraciones y condicionales) consiste en hacer 3 loops. Uno que sume los multiplos de 3 del 3 al 999, otro que sume los multiplos de 5 desde 5 al 999 y otro que sume los multiplos de 15 desde 15 al 999. Este último hay que hacerlo para restar los números que son multiplos comunes de 3 y 5 pues la suma previa va a dobletear el 15, 30, 45, 60... etc. Esto, evidentemente, también puede ser implementado en un sólo loop que lleve las sumatorias a partir de las condicionales o, más legible, que nomás contenga una condicional con un OR que tome en cuenta la sumatoria de múltiplos de 3 o de 5.

Hay otro método, más directo, si uno se acuerda de lo que le enseñaron en la escuela sobre series aritméticas y es el siguiente:

1. Tener en cuenta que el enésimo término de una serie aritmética


donde an es el enésimo término, a1 es el primero y
d es la diferencia común entre los números sucesivos de la serie.

2. Ahora bien, para obtener la sumatoria de esa serie se usa la siguiente fórmula (a mí se me olvida hasta que me acuerdo de la anécdota de Gauss consistente en que su profe de mate lo puso a sumar todos los números del 1 al 100 y él, después de una reflexión breve,obtuvo 5050 al darse cuenta que esa sumatoria es igual a tener 50 veces 101).


donde an es el enésimo término,
a1 el primer término y n es el total de términos en la serie.

3. Se substituye an
y después de simplificar se obtiene


donde n es el número de términos de la serie, lo que se obtiene muy fácil, por ejemplo, para saber cuántos términos tiene la serie de múltiplos de 3 hasta antes de llegar al 1000 hay que dividir 999 entre 3 y voila.

Ahora bien, se sustituyen valores y se obtienen los tres resultados de las sumatorias, sin que la computadora haga iteraciones a lo guey.

Multiplos de 3: 333/2 (2(3) + (333-1)3) = 166833

Multiplos de 5: 199/2 (2(5) + (199-1)5) = 99500

Multiplos de 15: 66/2 (2(15) + (66-1)15) = 33165

Se suman las dos primeras se resta la última y tan tan, da uno con la respuesta.

Si quieren aprender un lenguaje de programación nuevo o desempolvar uno que ya conozcan y afinar lo que saben de matemáticas les recomiendo ampliamente a registrarse en el Proyecto Euler, a resolver los problemas, a leer el código de otros participantes y a estudiar las soluciones que requieren poco o nulo tiempo de procesador.

pd. A los que resuelven todos los problemas, dicen, que les mandan una réplica del gorrito de Euler con el que se puede someter por control mental a parientes y amigos anuméricos. Dicen.

4 comentarios :

Kix dijo...

Ay, había olvidado lo maravillosas que son las mates... yo, hace añísimos que no programo ni me enfrento a ese tipo de situaciones. En mi chamba ya tengo más un rol administrativo que técnico! :-(

TheJab dijo...

A'i le envío mi comentario por formspring...

(Palabra verificadora: "ancer"... me suena a "answer"; espero obtenerla).

JRPB dijo...

Están bien enfermas algunas de las soluciones posteadas. Según yo muy old-school con gcc y autotools: apenas llevo 7 resueltos con métodos pocos elegantes. Excelente ejercicio para desempolvar el teclado. Tenía rato que no programaba nada de nada. Saludos, gracias por el link.

Ribozyme dijo...

Programar... una de las n mil cosas que un día quiero aprender en forma. En los tiempos en los que las víboras andaban paradas, aprendí a programar mi TI-59 y después BASIC, primero en una TRS-80 y después, en la facultad ¡en una MITS Altair 8800! que ya entonces era obsoleta (el primer producto comercial de Microsoft fue el BASIC para esa computadora). Era todo un viaje comunicarte con la computadora e imprimir a través de un teletipo.

¡Y qué chistoso que un lenguaje de programación se llame "paperas"!