Project Euler

Project Euler
Euler
Project Euler
URL 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 SOMME

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 :

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

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

  1. Depuis 2010, Project Euler existe aussi en français et en russe.
  2. 336 problèmes au 4 mai 2011
  3. 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. »
  4. C'est le OU inclusif qui est utilisé ici.
  5. 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

  1. (en)Project Euler - Problems sur projecteuler.net. Consulté le 4 mai 2011
  2. (en)Project Euler - Statistics sur projecteuler.net. Consulté le 4 mai 2011

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Project Euler de Wikipédia en français (auteurs)

Игры ⚽ Нужен реферат?

Regardez d'autres dictionnaires:

  • Project euler — Traduction à relire Project Euler → …   Wikipédia en Français

  • Project Euler — ] def multiple(i): return i % 3 = 0 or i % 5 = 0print sum(filter(multiple, range(1, 1000))) References External links * [http://projecteuler.net/ Home page] …   Wikipedia

  • Euler (disambiguation) — Euler may refer to: *Leonhard Euler, a Swiss mathematician and physicist *Carl Euler, a biologist *Ulf von Euler, a Swedish physiologist and pharmacologist, Nobel Prize in Medicine in 1970. *Hans von Euler Chelpin, a Swedish biochemist, Nobel… …   Wikipedia

  • Euler diagram — Euler diagrams or Euler circles are a diagrammatic means of representing sets and their relationships. They are the modern incarnation of Euler circles, which were invented by Leonhard Euler in the 18th century. Overview Euler diagrams usually… …   Wikipedia

  • Euler line — In geometry, the Euler line, named after Leonhard Euler, is a line determined from any triangle that is not equilateral; it passes through several important points determined from the triangle. In the image, the Euler line is shown in red. It… …   Wikipedia

  • Euler's theorem — In number theory, Euler s theorem (also known as the Fermat Euler theorem or Euler s totient theorem) states that if n is a positive integer and a is coprime to n , then:a^{varphi (n)} equiv 1 pmod{n}where φ( n ) is Euler s totient function and …   Wikipedia

  • Euler'sche Zahl — Die eulersche Zahl e = 2,718281828459... (nach dem Schweizer Mathematiker Leonhard Euler) ist eine irrationale und sogar transzendente reelle Zahl. Die eulersche Zahl ist die Basis des natürlichen Logarithmus und der (natürlichen)… …   Deutsch Wikipedia

  • Leonhard Euler — Infobox Scientist name = Leonhard Euler|box width = 300px |200px image width = 200px caption = Portrait by Johann Georg Brucker birth date = birth date|df=yes|1707|4|15 birth place = Basel, Switzerland death date = 18 September (O.S 7 September)… …   Wikipedia

  • Leonhard Euler — Retrato de Leonhard Euler, pintado por Johann Georg Bruck …   Wikipedia Español

  • Liste des sujets nommés d'après Leonhard Euler — En mathématiques et en physique, il existe un grand nombre de sujets nommés en l honneur de Leonhard Euler, dont beaucoup sont désignés par leur rôle : équation, formule, identité, nombre (unique ou séquence) ou une autre entité… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”