- Project Euler
-
Project EulerURL projecteuler.net Commercial non Type de site résolution de problèmes Langue(s) anglais[Note 1] Inscription gratuite Créé par Colin Hughes, alias 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 plus de 300 problèmes[Note 2],[1] de difficulté variable, chacun pouvant être résolu en principe en moins d'une minute par un algorithme efficace sur un ordinateur de puissance modeste. De nouveaux problèmes sont progressivement ajoutés, actuellement au rythme d'un par semaine, 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 7 niveaux de classement : les cinq premiers sont dénotés par les solides de Platon, le 6e par une sphère et le dernier, réservé aux vétérans à plus de 300 problèmes résolus, par une étoile. Il existe aussi un classement spécial basé sur la vitesse de résolution des derniers problèmes parus.
Depuis la création du site en 2001, plus de 150 000 utilisateurs se sont enregistrés sur le site[2].
Sommaire
Exemple de problème et solutions
Une traduction du premier problème est[Note 3] :
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[Note 4].
Bien que ce problème soit plus simple que le problème-type, il permet d'illustrer le gain de temps potentiel d'un algorithme efficace[Note 5] par rapport à un algorithme naïf. 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 ; en pseudo-code, cela peut s'écrire :
initialiser SOMME à 0; pour n variant de 1 à 999 faire si n mod 3 = 0 ou si n mod 5 = 0 alors ajouter n à SOMME; fait; renvoyer SOMMECependant, 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 1000. En notation de Landau, l'algorithme brute-force est en O(n) tandis que l'algorithme efficace est en O(1) (si on considère que le coût des opérations arithmétiques est constant).
Liens externes
Notes et références
Notes
- Depuis 2010, Project Euler existe aussi en français et en russe.
- 336 problèmes au 4 mai 2011
- L'énoncé original est « 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. »
- C'est le OU inclusif qui est utilisé ici.
- En informatique, quand un algorithme répond correctement au problème posé, on cherche souvent à l'optimiser. On veut que l'algorithme utilise le moins de temps et de mémoire possible. Voir ici pour plus de précisions.
Références
- (en)Project Euler - Problems sur projecteuler.net. Consulté le 4 mai 2011
- (en)Project Euler - Statistics sur projecteuler.net. Consulté le 4 mai 2011
- (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Project Euler » (voir la liste des auteurs)
Catégories :- Diffusion des mathématiques
- Algorithmique
Wikimedia Foundation. 2010.
