Project Euler: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
creo nuova voce |
Nessun oggetto della modifica |
||
| (40 versioni intermedie di 31 utenti non mostrate) | |||
Riga 1:
{{O|internet|novembre 2012}}
{{Sito web
| nome = Project Euler
▲| commerciale = no
| tipo = Sito di "[[problem solving]]"
| autore = Colin Hughes (aka euler)
| data di lancio = 5 ottobre, 2001
| proprietario = Coling Hughes
| registrazione = libera
| stato corrente = Attivo
| screenshot =
}}
'''Project Euler''' (
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 (comunicazione online)|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 ==
Il primo problema del Project Euler è:
<blockquote>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.
</blockquote>
Testo che tradotto in italiano, significa:
<blockquote> 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.<ref>Nota: questo è l'[[Disgiunzione inclusiva|OR inclusivo]] non quello [[Disgiunzione esclusiva|esclusivo]].</ref>
</blockquote>
Anche se questo problema è particolarmente semplice rispetto agli altri, esso illustra comunque la potenziale differenza di efficienza resa da un algoritmo efficiente. L'algoritmo [[Metodo forza bruta|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]]:
<pre>
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
</pre>
[[Python]]:
<syntaxhighlight lang="python">
print sum(x for x in xrange(1, 1000) if x%3==0 or x%5==0)
</syntaxhighlight>
[[C++]]:
<syntaxhighlight lang="cpp">
#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;
}
</syntaxhighlight>
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]].
: <math>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</math>
: <math>\sum_{i=1}^n ki = k\frac{(n)(n+1)}{2}</math>
Implementazione in python:
<syntaxhighlight lang="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)
</syntaxhighlight>
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 ==
<references/>
== Voci correlate ==
* [[Eulero]]
== Collegamenti esterni ==
* {{Collegamenti esterni}}
*{{cita web|http://euleres.zzl.org/|EulerES : Project Euler in spagnolo}}
*{{cita web | 1 = http://eulerdz.toile-libre.org/ | 2 = EulerDZ : Project Euler in francese | accesso = 8 maggio 2010 | urlarchivio = https://web.archive.org/web/20100522061217/http://eulerdz.toile-libre.org/ | dataarchivio = 22 maggio 2010 | urlmorto = sì }}
[[Categoria:Applicazioni dell'informatica]]▼
[[Categoria:Competizioni matematiche]]
[[Categoria:Iniziative web per la matematica]]
| |||