Le 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. Il tient son nom du mathématicien suisse Leonhard Euler qui a vécu au XVIIIème siècle.
Il comprend actuellement plus de 700 problèmes de difficultés variables, chacun pouvant être résolu en principe en moins d'une minute par un algorithme efficace sur un ordinateur de puissance modeste.
Ce challenge permet de découvrir des curiosités mathématiques, mais aussi d'améliorer ses compétences en programmation. Je me suis amusé à en résoudre quelques uns et je voulais vous partager mes découvertes.
La première énigme a pour énoncé :
Si nous énumérons tous les nombres naturels inférieurs à 10 qui sont des multiples de 3 ou 5, nous obtenons 3, 5, 6 et 9. La somme de ces multiples est 23.
Trouver la somme de tous les multiples de 3 ou 5 en dessous de 1000.
Une solution très facile
`somme = 0
for i in range(1000) :
if i%3==0 or i%5==0 :
somme = somme + i
print(somme) `
Pour décrire certains points pour les non-pythoniens, on pourrait parler de la fonction "range" qui permet d'itérer sur un nombre donné (ici de 0 à 9999). Le nombre passé en paramètre est "exclu" de l'itération. Cette fonction peut aussi être appelée avec 2 paramètres range(a,b) et dans ce cas, on va itérer de la valeur a (inclue) à la valeur b (exclue). Et dans le cas de 3 paramètres, on aura le "pas" comme 3ème paramètre. Ainsi :
>>> for i in range(10,2,-1):
... print(i)
...
10
9
8
7
6
5
4
3
Pour résumer :
- range(stop) prend un argument.
- range(start, stop) prend deux arguments.
- range(start, stop, step) prend trois arguments.
Et le deuxième point qui peut être intéressant est le % qui permet de calculer le "modulo", c'est à dire le reste de la division entière. Ainsi, 9 % 3 = 0 et si le reste de la division est zéro, c'est que le nombre est divisible par 3 et donc que c'est un multiple de 3.
Une solution plus complexe
Une suite arithmétique est une suite de nombres où l'on ajoute toujours la même valeur pour avoir le nombre suivant (exemple : 3, 6, 9, 12... on a ajouté 3 à chaque fois). La somme d'une suite arithmétique est donné par la formule : Sn = nombre de termes × (premier terme + dernier terme)/2
Mon prof de math au collège m'expliquait qu'il faut voir ça comme un escalier où chaque marche fait la même hauteur. Si on veut connaître la surface de l'escalier, il suffit de couper l'escalier en deux et d'en retourner la moitié pour l'emboiter sur l'autre. La plus grande marche coïncide avec la plus petite, la deuxième plus grande marche avec la deuxième plus petite etc.
Un dessin vaut mieux qu'un long discours :
Pour calculer la somme des nombres inférieur à 1000 divisibles par 3, il faudra faire la somme des 333 premiers nombres, on y ajoutera la somme des 200 premiers nombres de la suite arithmétique de raison 5 (c'est comme cela qu'on appelle l'incrément), mais il faudra aussi supprimer les multiples de 15 qui ont été compté 2 fois.
Comme vous pouvez le voir, une énigme peut se résoudre de différentes façons. Ici, la deuxième façon sera beaucoup plus rapide à exécuter que la première.
Si vous voulez me suivre sur Project Euler, vous pouvez ajouter ma clef pour m'avoir comme ami : 1891189_bX2ADi2zhlhONUJq1m0aezfIme4sbvXV
Et n'hésitez pas à me laisser votre clef en commentaire pour que je puisse vous suivre.
Top comments (0)