[Mini-Challenge Basic #8] : Comment tu paies ?

→ **MyCalcs** profile · by **Bisam** » 09 Jul 2014, 20:46

Aujourd'hui, vous ne saviez pas quoi faire et vous avez joué avec les centimes que vous aviez au fond de votre porte-monnaie en passant devant la machine à café.
Vous vous êtes demandé : "Si je n'utilise que des pièces (de 1, 2, 5, 10, 20, 50 centimes ou de 1 ou 2€), de combien de façons différentes puis-je payer mon café qui coûte 2€ au distributeur ?"

Maintenant, votre but dans la vie ne se résume qu'à cette question ! Serez-vous capable de créer une fonction qui prend comme arguments un entier n correspondant au nombre de centimes que vous devez payer et qui renvoie le nombre de façons de payer cette somme ?

Le vainqueur sera celui qui proposera la fonction la plus rapide.

Bonus à ceux qui trouvent une façon d'écrire l'algorithme en ayant comme deuxième argument les valeurs des pièces existantes (pour pouvoir s'adapter aux États-Unis, par exemple, où il n'y a pas de pièce de 20 mais une pièce de 25..., ou encore à la Poldévie dont les pièces valent 1, 3, 11, 19, 37 et 73 zloty)

Bonne chance !

PS : Toute ressemblance avec le Project Euler n°31 est totalement... voulue !

→ **MyCalcs** profile · by **Excale** » 09 Jul 2014, 21:33

Bonus: trouver le système optimal (j'ai ça quelque part mais je ne sais plus où) en prenant une distribution uniforme des prix.

→ **MyCalcs** profile · by **Bisam** » 09 Jul 2014, 21:41

Cela dépend du nombre de pièces différentes que tu autorises...
Il y a un article de Science&Vie (je crois) à ce sujet.

→ **MyCalcs** profile · by **critor** » 09 Jul 2014, 22:01

Tiens, c'est intéressant ça !

Sans aucune prétention au niveau des performances, voici un premier jet assez rapide:

Mes programmes · by **Levak** » 09 Jul 2014, 23:48

Bisam wrote:Vous vous êtes demandé : "Si je n'utilise que des pièces (de 1, 2, 5, 10, 20, 50 centimes ou de 1 ou 2€), de combien de façons différentes puis-je payer mon café qui coûte 2€ au distributeur ?"

Avant même de me demander ça, je suis déjà parti très loin de ce distributeur qui vend un café à 2€.

My calculator programs · by **Adriweb** » 09 Jul 2014, 23:49

C'était un distributeur de café dont les gobelets font 0.5L.

Sur ce, challenge intéressant indeed

→ **MyCalcs** profile · by **Bisam** » 10 Jul 2014, 08:24

Je n'ai pas cherché à tout comprendre dans ton algorithme, critor, et je n'ai pas du tout regardé s'il était performant mais tes réponses sont exactes.

Pour faire des tests de performance supplémentaires, essayez de trouver la réponse pour 15€ à payer (19 secondes sur ma calculette... pour un résultat égal à 3844287444)

→ **MyCalcs** profile · by **davidElmaleh** » 10 Jul 2014, 10:09

Je vais essayer de trouver une réponse convenable mais, entre temps, je reserve l'écriture de l'énoncé du challenge #9

→ **MyCalcs** profile · by **Hayleia** » 10 Jul 2014, 10:33

davidElmaleh wrote:Je vais essayer de trouver une réponse convenable mais, entre temps, je reserve l'écriture de l'énoncé du challenge #9

Nope, si tu veux écrire le challenge #9, il faut que tu gagnes le #8, pas d'arnaque

Sinon, ce problème me rappelle le problème du sac à dos et un exercice qu'il y avait eu au concours général

→ **MyCalcs** profile · by **davidElmaleh** » 10 Jul 2014, 10:46

Hayleia wrote:
davidElmaleh wrote:Je vais essayer de trouver une réponse convenable mais, entre temps, je reserve l'écriture de l'énoncé du challenge #9

Nope, si tu veux écrire le challenge #9, il faut que tu gagnes le #8, pas d'arnaque

Mon pauvre challenge #9...

Il va attendre longtemps alors et il devra changer de nom