Inscription / Connexion Nouveau Sujet
Rendu de monnaie
Bonjour
Je vous, propose le petit exercice simple suivant
Un caissier de magasin dispose d un nombre important de billets de 50, 20, 10 et 5€.
De combien de façon peut il rendre 100 € à un client
salut
Cliquez pour afficheren espérant bien compter ...
et je remercie par avance tous ceux qui me sortiront un super algo python (mais sans fonction trop exotique ou kabbalistique ou alors oui mais un autre sans) qui nous donne la solution ...
ty59847 : j'avais commencé avant toi et comme toi ... mais écrire tout m'a gonflé au bout de la vingtaine donc j'ai "résumé" !! 
Avant moi, c'est pas sûr. Ca m'a pris pas mal de temps pour tout taper !
Même si Copier/coller, c'est bien pratique !
quand j'ai commencé il n'y avait aucune réponse mais il est vrai que ça ne veut pas dire que tu n'avais pas commencé avant : j'ai bien du y passer un bon 1/4 d'heure à écrire toutes les solutions jusqu'à 0 * 50 et v * 20 avec v prenant les valeurs 5; 4, 3, 2 et 1 ...
puis je me suis mis à réfléchir ... et tout effacer pour reprendre avec des équations et le comptage des solutions .: en 2 mn et 60 s j'avais fini !!!
il est toujours bon de réfléchir avant de penser !!!
Un grand classique pour apprendre aux étudiants à utiliser la programmation dynamique et HJB
La bonne idée c'est de partir du résultat et d'essayer d'atteindre un point initial par soustractions
je remercie par avance tous ceux qui me sortiront un super algo python
A vos ordres
def monnaie(n):
billets = [5, 10, 20, 50]
billet_min = billets[0]
cache = {5: 1, 10: 2}
def monnaie_aux(n):
if n < billet_min:
cache[n] = 0
if n in cache:
return cache[n]
u = int(n in billets)
for billet in billets:
N = n - billet
possib_N = monnaie_aux(N)
if possib_N > 0:
u += possib_N
cache[n] = u
return u
return monnaie_aux(n)
print(monnaie(100))
et voici un code beaucoup plus dégueulasse et lent qui permet d'énumérer toutes les possibilités en prenant en compte ou pas l'ordre des billets. Sous-optimal, on peut faire bien mieux.
cache_aboule = {5: {(5,)}, 10: {(10,), (5,5)}}
billets = [5, 10, 20, 50] # toujours dans l'ordre croissant et non vide
billet_min = billets[0]
def aboule_le_fric(n):
if n == 0:
return set(tuple())
if n < billet_min:
return None
if n in cache_aboule:
return cache_aboule[n]
aboule_n = set()
for billet in billets:
N = n - billet
if N < billet_min:
break
if N not in cache_aboule:
cache_aboule[N] = aboule_le_fric(N)
aboule_N = cache_aboule[N]
if aboule_N is not None:
aboule_n |= set(map(lambda a: tuple(list(a)+[billet]), filter(lambda a: a is not None, aboule_N)))
if n in billets:
aboule_n |= {(n,)}
if len(aboule_n) == 0 or aboule_n == {None}:
aboule_n = None
cache_aboule[n] = aboule_n
return aboule_n
r = aboule_le_fric(100)
print("en prenant en compte l'ordre: ", len(r))
s = set(tuple(sorted(k)) for k in r)
print("à l'ordre près: ", len(s))
for u in s:
print(u)
Et le résultat que ça me sort:
Cliquez pour afficherOn peut aussi se passer de récursion, mais j'ai plus de place dans ce post
bravo à tous ! 
c'est bien 49 facons de faire
ma methode super rapide :
50x + 20y + 10z + 5 t = 100 est la meme chose que
10x + 4y + 2z + t = 20 .
x peut prendre les valeurs 0,1 ou 2 ( pas plus )
si x = 0 alors 4y +2z+t= 20
y peut prendre les valeurs {0,1,2,3,4,5}
si y =0 --> 2z+t = 20 -->z 
{0,1,2,...10} soit
11 solutions
si y =1 --> 2z+t = 16 -->z {0,1,2,...8} soit 9 solutions
si y =2 --> 2z+t = 12 -->z {0,1,2,...6} soit 7 solutions
si y =3 --> 2z+t = 8 -->z {0,1,2,3,4} soit 5 solutions
si y =4 --> 2z+t = 4 -->z {0,1,2 soit 3 solutions
si y =5 --> 2z+t = 0 -->z {0} soit 1 solution
si x = 1 ---> 4y+2z+t=10
y peut prendre les valeur 0,1 ou 2
si y =0 --> 2z+t = 10 -->z {0,1,2,...5} soit 6 solutions
si y =1 --> 2z+t = 6 -->z {0,1,2,3} soit 4 solutions
si y =2 --> 2z+t = 2 -->z {0,1} soit 2 solutions.
finalement si x = 2 alors 4y+2z+t=0 et ici c'est tres rapide
un seul triplet solution (2,0,0,0) soit 1 solution
total 
11 +9+7+5+3+1) + (6+4+2) + 1 = 49 solutions
10 on doit en rajouter 14
Bonjour lake,
il y a une imprécision dans ta formule :
l'équation où
n'a des solutions que si 5 divise
.
Il faut donc supposer que et alors
Annuler
connectez vous