Project Euler

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda
Project Euler
Leonhard Euler.jpg
Información general
Dominio http://projecteuler.net/
Tipo Sitio web
Comercial No
Idiomas disponibles Inglés
En español No
Estado actual Activo
Gestión
Desarrollador Colin Hughes
Lanzamiento 5 de octubre de 2001
Estadísticas
Usuarios registrados > 650 000
Ranking Alexa 41,408 (mayo de 2016)[1]
[editar datos en Wikidata]


Project Euler (Proyecto Euler, llamado después del matemático Leonhard Euler) es un sitio web dedicado a una serie de problemas matemáticos diseñados para ser resueltos por programas computacionales. El proyecto atrae a adultos y a estudiantes interesados en matemáticas y programación informática. Desde su creación en 2001 por Colin Hughes, Project Euler ha ganado notabilidad y popularidad internacional.[2]​ Incluye más de 575 problemas,[3]​ con uno nuevo siendo agregado cada fin de semana, excepto durante el verano. Los problemas varían de dificultad, pero todos son resolubles en menos de un minuto usando un algoritmo eficiente.[4]​ Un fórum específico para cada pregunta puede ser visitado después de que el usuario haya respondido correctamente a una pregunta dada. Para noviembre de 2016, Project Euler alcanzó a 650 000 usuarios alrededor del mundo que han resuelto al menos un problema.[5]

Los participantes pueden consultar su progreso mediante logros basados en el número de problemas resueltos. Un nuevo logro es alcanzado por cada 25 problemas resueltos. Existen premios especiales por resolver combinaciones de problemas especiales; por ejemplo, hay un logro ofrecido por resolver cincuenta problemas numerados como primos. También existe un nivel especial para registrar logros basados en los cincuenta primeros usuarios que resuelven problemas nuevos.[6]

Un subset de problemas de Project Euler fue usado en un concurso de programación de APL.[7]​ Hay 97 secuencias en la Enciclopedia Electrónica de Secuencias de Enteros (OEIS) referenciadas en problemas de Project Euler.[8]

Problemas y soluciones de ejemplo[editar]

El primer problemas de Project Euler es:[9]

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

Si listamos todos los números naturales menores de 10 que son múltiplos de 3 o 5, conseguimos 3, 5, 6 y 9. La suma de estos múltiplos de 23.

Encuentra la suma de todos los múltiplos de 3 o 5 menores de 1000.[note 1]

Aunque este problema es mucho más simple que los tradicionales, sirve para ilustrar la gran diferencia que un algoritmo eficiente hace. El algoritmo de fuerza bruta examina cada número natural menor a 1000 y realiza una suma de aquellos que cumplen estos requisitos. Este método es sencillo de implementar, como se indica en el siguiente pseudocódigo:

Set TOTAL to 0;
for NUM from 1 through 999 do
  if NUM mod 3 = 0 or if NUM mod 5 = 0 then
    add NUM to TOTAL;
output TOTAL

Para problemas más difíciles, se vuelve más importante encontrar un algoritmo eficiente. Para este problema, podemos reducir 1000 operaciones a unas pocas usando el principio de inclusión-exclusión y usando una sumatoria de forma cerrada:

Aquí, denota una suma de varias menores de .

En una cota superior asintótica, el algoritmo de fuerza bruta es O(n) y el algoritmo eficiente es O(1) (asumiendo tiempo constante de operaciones aritméticas).

Notas[editar]

  1. Este es el O inclusivo, no el O exclusivo

Referencias[editar]

  1. «Projecteuler.net Site Overview». Alexa Internet. Consultado el 30 de mayo de 2016. 
  2. James Somers (Junio de 2011). «How I Failed, Failed, and Finally Succeeded at Learning How to Code - Technology». The Atlantic. Consultado el 14 de diciembre de 2013. 
  3. «Project Euler (lista de problemas)». Consultado el 2 de noviembre de 2016. 
  4. «Project Euler - About». Consultado el 4 de abril de 2008. 
  5. Hughes, Colin. «About - Project Euler». projecteuler.net. Consultado el 6 de julio de 2016. 
  6. «Project Euler (Noticias)». Consultado el 31 de marzo de 2015. 
  7. «APL programming contest problem list». Consultado el 17 de agosto de 2014. 
  8. «OEIS sequences referencing Project Euler problems». Consultado el 30 de mayo de 2016. 
  9. «Project Euler Problem 1». Project Euler. Consultado el 1 de marzo de 2017. 

Enlaces externos[editar]