UNIVERSIDAD PRIVADA DOMINGO SAVIO
FACULTAD DE TECNOLOGÍA
CARRERA DE INGENIERÍA EN SISTEMAS
Perfil de Proyecto:
PROYECTO EULER
Presentado por:
APELLIDOS Y NOMBRES
[Link].2014
Cochabamba, Bolivia
INTRODUCCIÓN
Project Euler es una web de problemas numérico-lógicos y de programación que lleva el
nombre del famoso matemático. Allí se proponen retos que supongan pensar «con algo
más que una mente puramente matemática», de modo que para resolver el problema
haga falta programarlo en algún lenguaje. Algunos de los retos son, por ejemplo:
Sumar todos los números naturales menores de 1.000 que sean múltiplos de 3 o 5
Calcular todas las letras que hacen falta para escribir «de palabra» los números
entre 1 y 1.000
¡Sumar todos los dígitos de 100! (factorial de 100)
¿Con cuántas manos distintas gana la partida el primer jugador en una partida de
póker (dos jugadores)?
Sumar todos los primos por debajo de 1.000.000
(Las soluciones a estos problemas están en la lista de retos planteados.)
Para complicarlo un poco se sugiere que el programa que calcule la solución debe poder
dar un resultado en menos de un minuto.
La lista de problemas supera ya los 160 y hay unos 6.800 usuarios activos de un montón
de países. En la interesante página de estadísticas puede verse qué tipo de lenguajes
utilizan los programadores, desde «lápiz y papel» a C/C++ (que gana por goleada), algo de
Python y también Java, Haskell, Ruby y otros muchos.
OBJETIVO
La idea del proyecto es presentarte una serie de desafíos matemáticos, y la misión es
resolverlos usando un programa en cualquier plataforma (hasta el papel y el lápiz sirve) y
entregar la respuesta. No es una competencia, bueno si es competencia, pero es la que te
planteas contra tu propia capacidad de resolver estos problemas. Los primeros son
bastante sencillos pero la dificultad crece bastante rápido, aunque no son imposibles de
resolver. La utilidad de estos ejercicios es en el caso mío al menos la posibilidad de
refrescar las miserables habilidades matemáticas conseguidas en años y volver a pensar
en la despreciada optimización.
CONTENIDO DEL PROYECTO EULER
El uso del lenguaje
Java
Para cada problema que he resuelto, tengo una solución Java para él (y posiblemente
código en otros idiomas también). Me gusta el uso de Java, ya que es rápido, seguro y
expresivo. Para más detalles sobre estos puntos, me comparo con otros lenguajes de
programación: Python y Mathematica son lentos para la aritmética de enteros básica (~
1/30 × velocidad de Java), ya que de forma nativa utilizan bigint y también se escriben de
forma dinámica. Además, Mathematica utiliza una gran cantidad de memoria para
almacenar una matriz de enteros, ya que no ha empacado enteros de ancho fijo. C y C ++
son inseguras debido a la falta de límites de la matriz de comprobación, que han firmado
desbordamiento de entero, y que tienen toneladas de invocarse fácilmente
comportamientos no definidos. estructuras de datos personalizados, como los gráficos
son difíciles de expresar limpiamente en Mathematica. algoritmos personalizados, como la
criba de Eratóstenes, especialmente las expresadas más natural en cuanto a las
actualizaciones de estado imperativas, son difíciles de aplicar correctamente o de manera
eficiente en Haskell. Valoración no estricta en Haskell hace que sea fácil de fuga accidental
de grandes cantidades de memoria en lugares inesperados.
Sin embargo en la otra cara, prefiero resolver un problema en Mathematica primero si es
posible. Esto es porque tiene muchos útiles funciones integradas de matemáticas (como
prueba prima) y objetos (como fracciones) que requeriría un esfuerzo manual para
implementar en Java. Además, mis soluciones Java tienden a ser largos debido a los tipos
en todas las variables, una gran cantidad de código personalizado, y los bucles en lugar de
funciones de orden superior de bajo nivel. Si yo era el objetivo de la velocidad de
ejecución en bruto, la escritura de código comparable en C o C ++ probablemente ejecutar
3 × tan rápido como Java.
Nótese que para los problemas que implican números no enteros, intento utilizar
aritmética exacta número entero o fracciones tanto como sea posible, lo que asegura que
la solución es demostrablemente correcta. Como resultado evito enérgicamente cualquier
aritmética de punto flotante en absoluto, a menos que no hay otra manera razonable (que
yo sepa) para solucionar el problema. También estudio de los límites numéricos con
cuidado para evitar desbordamiento de entero, y utilizar el tipo más razonablemente
limitada por la velocidad (elegir entre int, longo BigInteger).
Para ejecutar una solución de Java, compile el archivo Java (por ejemplo [Link]) y
también las clases compartidas [Link] [Link]. A continuación, ejecute
con un comando como java p001, y la respuesta será impreso en la salida estándar.
Código de la muestra (problema 117) (la mayoría de las otras soluciones son muchas veces
más largos):
p117 clase pública {
privado static final int Longitud = 50;
principales (args String []) {public static void
// Programación dinámica
de largo [] maneras = new largo [LONGITUD + 1];
maneras [0] = 1;
for (int n = 1; n <= longitud; n ++) {
for (int k = 1; k <= 4 && k <= n; k ++)
maneras [n] + = maneras [n - k];
}
[Link] (maneras [LONGITUD]);
}
}
recursos:
Sitio Oficial: Oracle Java
Python
Muchas soluciones se ponen a disposición en Python, que es un lenguaje orientado a
objetos imperativo con muchas similitudes conceptuales a Java. Estas piezas de código son
interesantes para un par de razones: Una es que abastece a los programadores que
prefieren leer el código Python sobre Java debido a la familiaridad con el idioma. Otra es
que el código Python tiene “ruido” menos sintáctica debido a la falta de tipos, las
declaraciones de variables, y las diferencias de tamaño entero - por lo que el código
Python expresa las ideas esenciales de los algoritmos matemáticos más directamente. Mi
código Python está diseñado para ser compatible con Python 2.7 y 3.4 por igual.
Las soluciones de Python se basaron inicialmente en las soluciones de Java, a menudo a
partir de un puerto literal directa del código de Java en Python. Con el tiempo, el código
Python fue adaptado para ajustarse a las características de la lengua - como el uso de
enfoques idiomáticas / Pythonic, ajustar o cambiar los algoritmos para aumentar la
velocidad (mientras que Java a veces puede salirse con algoritmos menos eficientes, pero
más simple), y hacer un uso intensivo de los generadores. El estilo de la utilización de
generadores / filtros / itertoolsse puede considerar a mitad de camino entre el estilo
imperativo de Java y estilo funcional Haskell {o} Mathematica 's. Desafortunadamente,
debido a un rendimiento lento de Python en las matrices y los valores de entero corto,
será difícil para mí hacer soluciones Python disponibles para la CPU o problemas Proyecto
Euler intensivo de la memoria.
Código de la muestra (problema 10):
# Criba de Eratóstenes
ans = 0
ISPrime = [Real] * 2000001
para i en el rango de (2, len (ISPrime)):
si ISPrime [i]:
ans + = i
para j en el rango (i * i, len (ISPrime), i):
ISPrime [j] = False
impresión (ans)
recursos:
Sitio Oficial: [Link]
Mathematica
Usé Mathematica para muchos de los problemas anteriores, ya que las funciones de la
biblioteca de compacidad y conveniente eran más importantes que el tiempo o la
memoria en funcionamiento. Mathematica proporciona un fácil acceso a los números
primos, números enteros grandes, flotadores de alta precisión, fracciones, las fracciones
continuas, y mucho más. Mi código tiende a ser bastante corto: de una sola línea son muy
comunes, y típicamente la solución es menor que 5 líneas de código. Para los problemas
que implican la informática y / o almacenar millones de números, mi experiencia ha sido
que Mathematica toma demasiado tiempo para ejecutar mi algoritmo o excede el límite
de memoria.
En Mathematica, hago un uso intensivo de las expresiones anidadas, funciones básicas de
programación funcional como Mapy Select, y las funciones de agregación
como Total, Length, Sum. De vez en cuando escribo código imperativo en Mathematica,
por lo general para la búsqueda ilimitada. Escribo código Mathematica en un estilo
bastante sencilla, utilizando sólo []para aplicación de función (no @o //), evitar el
procesamiento de patrones, y evitar que se declara funciones con el #-y- &sintaxis.
Para ejecutar una solución de Mathematica, copiar el código completo en un nuevo
cuaderno de Mathematica y evaluar todo el bloque de texto. La solución se muestra en la
salida.
Código de la muestra (problema 7):
Primer [10001]
Código de la muestra (problema 20):
Total [IntegerDigits [100]]
Código de la muestra (problema 29):
Longitud [Unión [Aplanar [Tabla [a ^ b, {a, 2, 100}, {b, 2, 100}]]]]
Código de la muestra (problema 323):
cdf [n_]: = (1 - (1/2) ^ n) ^ 32
pdf [n_]: = cdf [n] - cdf [n - 1]
Suma [n * pdf [n], {n, Infinito}] (* * exacta)
N [%, 11] (* redondeado *)
recursos:
Sitio Oficial: Wolfram Mathematica
Referencia de las funciones: Wolfram Mathematica Documentación
HASKELL
Soy un principiante en la programación Haskell, y sólo sé cómo usarlo para resolver los
problemas más fáciles de Project Euler. Cuando lo uso, me acaban de aprender muchos
conceptos nuevos en la programación funcional, tales mapa / filtro / pliegue, listas
infinitas, la conversión de algoritmos iterativos a las funciones recursivas, memoization,
etc. Cuando un problema se puede resolver de una manera puramente funcional sin
imperativamente la actualización de las variables, mi solución Haskell se estructurará de
manera muy similar a mi solución de Mathematica.
Para ejecutar una solución Haskell, ejecute el archivo Haskell como programa principal.
Código de la muestra (problema 21):
principal = putStrLn (mostrar ans)
ans = suma [n | n <- [1..10 ^ 4], amistosa n]
amistosa :: Int -> Bool
amistosa n = dejar que m = divisorSum n en (m / = n) && (divisorSum m) == n
divisorSum :: Int -> Int
divisorSum n = suma [k | k <- [1..n-1], (nk mod) == 0]
recursos:
Sitio Oficial: El lenguaje de programación Haskell
Tutorial: Aprende Eres una Haskell para gran bien!
TIEMPOS DE REFERENCIA
Los programas de solución Proyecto Euler nombrados fueron punto de referencia para ver
cuánto tiempo que tomó para calcular la respuesta. Esta información da una idea
aproximada de qué problemas son fáciles o difíciles, y cómo la elección del lenguaje de
programación afecta el tiempo de ejecución.
Tenga en cuenta que el punto de referencia no trata de ser “justo” de ninguna manera. Mi
código de la solución es primero diseñado para funcionar dentro de un tiempo de
funcionamiento “aceptable” (no la orientación absoluta de código más rápido), y luego
muy optimizado para mayor claridad humana (tanto en términos de la implementación
del código y los conceptos matemáticos subyacentes). A veces, los constructos
ligeramente ineficientes (tales como listas por comprensión) se utilizan en aras de la
claridad. Los algoritmos entre las diferentes lenguas no son exactamente los mismos; en
lugar de eso trato de escribir código que es más idiomática y clara del idioma en
cuestión. Sin embargo, todavía se puede observar que Python es generalmente de 10 × 30
× a más lento que Java para código de procesamiento de datos numéricos puro.
Todos los números que aparecen en la siguiente tabla están en segundos, y se utilizaron
estos entornos informáticos:
Oracle Java 1.8.0 Actualización 45 (64 bits), Intel Core i5-4690 (Haswell) 3.50 GHz,
Windows 8.1 Pro (64 bits)
CPython 2.7.10 (64 bits), Intel Core i5-4690 (Haswell) 3.50 GHz, Windows 8.1 Pro
(64 bits)
CPython 3.5.1 (64 bits), Intel Core i5-4690 (Haswell) 3.50 GHz, Windows 8.1 Pro (64
bits)
Wolfram Mathematica 5.1, Intel Core 2 Q6600 (Kentsfield) 2.40 GHz, Windows XP
SP3 Pro (32 bits)
ANÁLISIS
Si perteneces al grupo de personas que gustan de enfrentarse a un buen desafío, Project
Euler es ideal para ti. Se trata de una serie de problemas que
involucran matemáticas y programación, que los aficionados deben intentar resolver. En
este momento hay 309 problemas propuestos, y en pocas horas estará disponible el
número 310. ¿Te animas a ser el primero en resolverlo?
No son pocos los programadores que gustan de los problemas matemáticos. También es
cierto que a muchos matemáticos les gusta programar. A ambos grupos seguramente les
interesará conocer el denominado Project Euler, una colección de desafíos que requieren
de talento matemático y habilidades relacionadas con la programación para ser resueltos.
El objetivo del proyecto es simplemente estimular a los participantes a
desarrollar mejores habilidades de programación, aprender conceptos nuevos y -sobre
todo- divertirse. El nombre de este proyecto honra a Leonhard Euler, el brillante
matemático y físico suizo cuyo aporte más conocido es el número de Euler (e ≈ 2.71828),
utilizado como base del logaritmo natural. Euler realizó trabajos relacionados con el
Cálculo infinitesimal, la Teoría de Grafos, la dinámica de fluidos, óptica y astronomía. Por
todo esto se lo considera uno de los matemáticos más importantes de todos los tiempos.
Los problemas propuestos (periódicamente se van agregando nuevos) suelen ser bastante
complicados, pero con un poco de imaginación, habilidad matemática y una buena dosis
de lógica, los podrás resolver. Para conocerlos no hace falta registrarse. Con solo visitar la
web puedes acceder a la lista de problemas disponibles y comenzar a resolverlos. Pero si
quieres ir “sumando puntos” a medida que los resuelves, puedes crearte una cuenta de
usuario (solo necesitas unos segundos para hacerlo), y comenzar a recorrer la lista de
problemas como todo un profesional.
Un aspecto interesante del Project Euler es que -si los encaras de la forma correcta- los
problemas propuestos se resuelven utilizando un ordenador poco potente en menos de
un minuto.
Por ejemplo, el problema número 48 dice:
“Encuentra los últimos 10 dígitos de la serie 1¹ + 2² + … + 1000¹⁰⁰⁰.”
Está claro que utilizando “fuerza bruta” eso no se resuelve en menos de un minuto, por lo
que deberás concentrarte en encontrar un algoritmo eficiente que te evite esperar años
mientras tu pobre ordenador trabaja.
