Project Euler

Da Wikipedia, l'enciclopedia libera.
Project Euler
Euler
URL projecteuler.net
Commerciale No
Tipo di sito Sito di "problem solving"
Registrazione libera
Proprietario Coling Hughes
Creato da Colin Hughes (aka euler)
Lancio 5 ottobre, 2001
Stato attuale Attivo

Project Euler (anche conosciuto in italia come Progetto Eulero) è un sito dedicato a una serie di problemi matematici da risolvere realizzando dei programmi per computer. Il progetto ha coinvolto adulti e studenti interessati alla matematica e alla programmazione e include molteplici problemi di varia difficoltà, ognuno di essi risolvibile in meno di un minuto utilizzando un algoritmo efficiente su un computer di media potenza.

Vengono inoltre proposti nuovi problemi periodicamente sin dalla creazione del progetto, avvenuta nel 2001. Col sito, è stato creato anche un forum dedicato dove l'utente può discutere degli esercizi una volta risolti, infatti è permesso accedere al thread soltanto dopo aver risolto l'esercizio corrispondente. Oltre alla pagina dedicata del forum, una volta risolto un dato problema è spesso disponibile anche una soluzione proposta dai creatori del sito con una o più varianti che riassumono le versioni più efficienti che si potevano trovare per risolvere l'esercizio.

È inoltre accessibile per gli utenti registrati anche una sezione che ordina gli utenti per il numero di problemi risolti. Sono definiti 14 livelli di punteggio, dove ognuno di essi scatta ogni 25 problemi risolti. Si parte dal livello 0 (fino a 25 problemi risolti) fino ad arrivare al 13° (325+). Vi sono inoltre 21 piccoli premi intermedi ("Decathlete": risolvi 10 problemi consecutivi, "Centurion": risolvi 100 problemi consecutivi, "One In A Hundred": sii tra i primi 100 a risolvere un problema, e così via).

Il sito consta di 362 problemi in data 12 dicembre 2011.

Esempio di un problema e la sua risoluzione[modifica | modifica sorgente]

Il primo problema del Project Euler è:

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.

Testo che tradotto in italiano, significa:

Se elenchiamo tutti i numeri naturali fino al 10 che sono multipli di 3 o di 5, otteniamo 3, 5, 6 e 9. La somma di tutti i multipli è 23.

Trova la somma di tutti i multipli di 3 o di 5 sotto 1000.[1]

Anche se questo problema è particolarmente semplice rispetto agli altri, esso illustra comunque la potenziale differenza di efficienza resa da un algoritmo efficiente. L'algoritmo brute-force esamina ogni numero naturale inferiore a 1000 e tiene una variabile che contiene la somma dei numeri che corrispondono al criterio dato. Il metodo è semplice da implementare, com'è mostrato dagli esempi che seguono nei diversi linguaggi di programmazione:

Pseudocodice:

Set TOTAL to 0;
for every number NUM from 1 to 1000 do
  if NUM mod 3 = 0 OR if NUM mod 5 = 0 then
    add NUM to TOTAL;
OUTPUT total

Python:

print sum(x for x in xrange(1, 1000) if x%3==0 or x%5==0)

C++:

#include <iostream>
using namespace std;
int main( ) {
  int sum = 0;
  for (int i = 0; i < 1000; i++)
    if ( i % 3 == 0 || i % 5 == 0 )
      sum += i;
  cout << sum << endl;
  return 0;
}

Per i problemi più complicati, diventa importante trovare un algoritmo efficiente. Per questo problema, possiamo ridurre di molto i calcoli utilizzando il principio di inclusione ed esclusione e una sommatoria.

sum(n) = \sum_{i=1}^{\left \lfloor \frac{n}{3} \right \rfloor} 3i + \sum_{i=1}^{\left \lfloor \frac{n}{5} \right \rfloor} 5i - \sum_{i=1}^{\left \lfloor \frac{n}{15} \right \rfloor} 15i
\sum_{i=1}^n ki = k\frac{(n)(n+1)}{2}

Implementazione in python:

def sum1toN(n):
   return n * (n + 1) / 2
 
def sumMultiples(limit, a):
   return sum1toN((limit - 1) / a) * a
 
sumMultiples(1000, 3) + sumMultiples(1000, 5) - sumMultiples(1000, 15)

Nella notazione O-grande, l'algoritmo a forza bruta è O(n) e l'algoritmo efficiente è O(1) (assumendo costante il tempo per le operazioni aritmetiche).

Voci correlate[modifica | modifica sorgente]

Note[modifica | modifica sorgente]

  1. ^ Nota: questo è l'OR inclusivo non quello esclusivo.

Collegamenti esterni[modifica | modifica sorgente]