Project Euler
Project Euler (conosciuto anche 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.
Project Euler sito web | |
---|---|
URL | projecteuler.net/ |
Tipo di sito | Sito di "problem solving" |
Registrazione | libera |
Commerciale | No |
Proprietario | Coling Hughes |
Creato da | Colin Hughes (aka euler) |
Lancio | 5 ottobre, 2001 |
Stato attuale | Attivo |
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 è a volte 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.
Il sito consta di 822 problemi in data 24 dicembre 2022.
Esempio di un problema e la sua risoluzione modifica
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:
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
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-esclusione e una sommatoria.
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).
Note modifica
- ^ Nota: questo è l'OR inclusivo non quello esclusivo.
Voci correlate modifica
Collegamenti esterni modifica
- Sito ufficiale, su projecteuler.net.
- EulerES : Project Euler in spagnolo, su euleres.zzl.org.
- EulerDZ : Project Euler in francese, su eulerdz.toile-libre.org. URL consultato l'8 maggio 2010 (archiviato dall'url originale il 22 maggio 2010).