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 à :

• Prendre \(a\), \(b\), \(c\), \(d\), \(e\), \(f\), \(g\) et \(h\), correspondant respectivement au nombre de pièces de £2, £1, 50p, 20p, 10p, 5p, 2p et 1p, tel que \(200a + 100b + 50c + 20d + 10e + 5f + 2g + h = 200\)
• faire varier tous ses coefficients en gardant à l'esprit que comme ils sont forcément positifs, nous avons les inéquations suivantes :
  $$\begin{cases}
  100b \le 200 - 200a \\
  50c \le 200 - 200a - 100b \\
  20d \le 200 - 200a - 100b - 50c \\
  10e \le 200 - 200a - 100b - 50c - 20d \\
  5f \le 200 - 200a - 100b - 50c - 20d - 10e \\
  2g \le 200 - 200a - 100b - 50c - 20d - 10e - 5f \\
  ​f \le 200 - 200a - 100b - 50c - 20d - 10e - 5f - 2g
  \end{cases}​$$

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.