Project Euler

Cygal — Sat, 19 May 2007 16:47:00 +0000

De la présentation d'un « projet » qu'il est bien.

Ou comment résoudre des problèmes mathématiques avec les outils qui vous plaisent, quels qu'ils soient.

Le principe de Project Euler est très simple : vous vous inscrivez (c'est rapide), et vous avez à votre disposition de nombreux problèmes « mathématiques » (155 à l'heure où je vous écris), pour la plupart assez originaux, et en tout cas assez amusants, des plus simples aux plus ardus. Les premiers permettent de se mettre en jambe, voyez vous-même (ceci est le problème classé comme le plus facile) :

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.

Pour les anglophobes, sachez que le but est de trouver la somme de tous les multiples de 3 et 5 inférieurs à 1000. Vous l'aurez remarqué : faire ce calcul à la main peut s'avérer difficile. Tout l'intérêt est de trouver un autre moyen, qu'il soit plutôt mathématique ou informatique. Au fur et à mesure des problèmes, la difficulté augmente, dans le sens où un calcul non réfléchi ou qui utilise la force brute ne suffit tout simplement pas car le calcul serait bien trop long. Les concepteurs des problèmes le font parfois remarquer lourdement :

It is not possible to try every route to solve this problem, as there are 299 altogether! If you could check one trillion (1012) routes every second it would take over twenty billion years to check them all. There is an efficient algorithm to solve it. ;o)

Note : Vous n'aurez pas le droit à une traduction cette fois, bien fait pour vous !

Vous êtes donc obligés, en raison des nombres relativement élevés, de chercher une optimisation de l'implémentation naïve. Le plus impressionnant est que les concepteurs assurent que tous les problèmes peuvent être résolus sur une machine modeste en moins d'une minute. Tout le fun est alors dans la recherche de l'algorithme ! Celle-ci n'est parfois pas simple, et c'est là tout l'intérêt. Alors que trouver la somme de tous les multiples de 3 et 5 inférieurs à 1000 est trivial, trouver les 40 premiers facteurs du nombre constitué d'un milliard de 1 l'est déja moins. :P

Le but avoué est de permettre à n'importe quel public de découvrir de nouveaux concepts, et de faire ceci tout en s'amusant avec son langage préféré. C'est un des aspects les plus intéressants : le moyen utilisé importe peu, et cette liberté permet de comparer différentes manières de résoudre un même problème. Lorsque vous avez résolu un problème, il est possible de voir les solutions des autres membres (qui sont nombreux), ce qui est parfois très enrichissant (surtout quand c'est de l'asm x86 :D). Au vu de ce succès, le Project Euler est un projet réussi.

Dissidents - Maths

Project Euler