Lucas Willems

LUCAS WILLEMS

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

English

Project Euler 31 : solution Python

Article

Voici un résumé de l'énoncé du problème 31 "Coin sums" du Project Euler (traduction complète en français ici) :

How many different ways can £2 be made using any number of coins ? (voir énoncé complet)

Compréhension du problème

Reformulons le problème : il nous faut trouver le nombre de manières différentes d'obtenir £2 (200p) en utilisant n'importe quelle pièce. Pour résoudre ce problème, nous pouvons procéder de manière brute force, manière sûrement non optimale mais qui permet d'obtenir le résultat très rapidement quand même. Cette manière consiste donc à :

Le programme

Voici le programme Python que nous pouvons alors utiliser pour résoudre ce problème :

resultat = 0
reste = 200
for a in range(0, reste+1, 200):
    reste = 200 - a
    for b in range(0, reste+1, 100):
        reste = 200 - a - b
        for c in range(0, reste+1, 50):
            reste = 200 - a - b - c
            for d in range(0, reste+1, 20):
                reste = 200 - a - b - c - d
                for e in range(0, reste+1, 10):
                    reste = 200 - a - b - c - d - e
                    for f in range(0, reste+1, 5):
                        reste = 200 - a - b - c - d - e - f
                        for g in range(0, reste+1, 2):
                            h = 200 - a - b - c - d - e - f - g
                            if h >= 0:
                                resultat += 1
print(resultat)

Le résultat

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

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.