Lucas Willems

LUCAS WILLEMS

Un étudiant de 21 ans passionné par les maths et la programmation

English

Project Euler 9 : solution Python

Article

Voici un résumé de l'énoncé du problème 9 "Special Pythagorean triplet" du Project Euler (traduction complète en français ici) :

Find the product abc for which there exists exactly one Pythagorean triplet for which \(a+b+c=1000\).

Compréhension du problème

Reformulons le problème : il nous faut trouver le produit \(a \times b \times c\) d'une triplette Pythagorienne, c'est à dire le produit des 3 longueurs des côtés d'un triangle rectangle, avec \(a+b+c=1000\).

Je pense que vous avez une petite idée de comment résoudre le problème : il va nous falloir faire varier les valeurs de a, b et c tant que \(a+b+c \ne 1000\) ou \(a^2+b^2 \ne c^2\). Nous savons aussi, grâce à l'énoncé, que \(a<b<c\).

Toutefois, cet aperçu de la solution n'est pas encore suffisant, il nous faut réfléchir sur comment "faire varier les valeurs de a, b et c" car faut-il faire varier les 3 valeurs ? et sur quel intervalle ? Pour répondre à la première question, nous n'avons pas besoin de faire varier les 3 valeurs, en faire varier 2 suffit car si nous connaissons, par exemple, la valeur de c et b, nous pouvons en déduire celle de a en résolvant l'équation vue plus haut \(a+b+c=1000\). En ce qui concerne l'intervalle, comme nous savons aussi que \(a<b<c\), nous pouvons en déduire que \(335 \le c\), \(334 \le b\) et que \(331 \le a\). La réponse à ces 2 questions nous donne maintenant un aperçu satisfaisant de la façon de résoudre ce problème.

Le programme

Voici le programme Python que l'on obtient pour résoudre le problème si nous suivons les réflexions précédentes :

c = 335
b = 334
a = 1000 - c - b
while a + b + c != 1000 or a**2 + b**2 != c**2:
    if a > b or b == 2:
        c += 1
        b = c - 1
    b -= 1
    a = 1000 - c - b
print(a*b*c)

Comme toutes les explications ont été données plus haut, je ne pense pas avoir besoin d'ajouter des commentaires sur ce code.

Le résultat

La réponse à ce problème est 31875000.

Recherche

Voici les recherches relatives à cette page :

Commentaires

Qu'en pensez-vous ? Donnez moi votre avis (positif ou négatif) pour que je puisse l'améliorer.