Project Euler

URL	projecteuler.net
Commercial	non
Type de site	résolution de problèmes
Langue(s)	anglais
Inscription	gratuite
Créé par	Colin Hughes (aka Euler)
Lancement	5 octobre, 2001
État actuel	en activité

Project Euler est un site web proposant une série de problèmes mathématiques conçus pour être résolus à l'aide de programmes informatiques. Le but du projet est d'attirer des adultes et des élèves intéressés par les mathématiques et l'informatique. Il comprend actuellement près de 300 problèmes de difficulté variable, chacun pouvant être résolu en moins d'une minute par un algorithme efficace sur un ordinateur de puissance modeste. De nouveaux problèmes ont été progressivement ajoutées depuis la création du site en 2001. Un forum spécifique à chaque problème est accessible aux utilisateurs qui l'ont résolu. Une section Scores classe également les membres selon le nombre de problèmes résolus. Il existe 6 différents niveaux de classement (les cinq premiers dénotés par les solides de Platon, le 6ème par une sphère), plus un classement spécial basé sur les derniers problèmes pour les utilisateurs les plus rapides.

Une traduction du premier problème est :

Si on liste tous les entiers naturels inférieurs à 10 qui sont multiples de 3 ou de 5, on obtient 3, 5, 6 et 9. La somme de ces nombres est 23. Trouvez la somme de tous les multiples de 3 ou de 5 inférieurs à 1000.

Bien que ce problème soit plus simple que le problème type, il permet d'illustrer la différence potentielle effectuée par un algorithme efficace. L'algorithme brute-force examine chaque entier naturel inférieur à 1000 et actualise la somme de ceux qui remplissent les critères. Cette méthode est facile à implémenter, comme le montrent les exemples suivants dans différents langages de programmation :

PHP:

Python:

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

C++:

#include 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; }

Java:

public class Main { public static void main(String[] args) { int sum = 0; for (int i = 0; i < 1000; i++) if ( i % 3 == 0 || i % 5 == 0 ) sum += i; System.out.println(sum); } }

JavaScript:

var sum = 0; for(var i = 1; i < 1000; i++) { if(i % 3 || i % 5) sum += i; } alert(sum);

Cependant pour les problèmes plus complexes, trouver un algorithme efficace devient indispensable. Pour cet exemple, nous pouvons réduire 1000 opérations à quelques unes en utilisant le principe d'inclusion-exclusion et une formule de sommation :

Implémentation en 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)

Grâce à cet algorithme, la solution pour une borne supérieure à 10 000 000 peut être obtenue aussi rapidement que pour 1 000. En notation de Landau, l'algorithme brute-force est en O(n) tandis que l'algorithme efficace est en O(1) (en considérant le coût des opérations arithmétiques comme constant).