Il s'agit de résoudre une énigme avec son PC plutôt qu'en écrivant des équations et en appliquant des théorèmes. L'énigme a été posée au Championnat International de jeux mathématiques en 2000, dans la catégorie la plus relevée. J'ai trouvé l'énoncé ICI, exercice 15. Je vous le donne tel quel, je crois qu'il n'est pas difficile à comprendre :
Citation : Monnaie syldave
Audrey passe ses vacances en Syldavie. Dans ce pays, les pièces de
monnaie n'ont plus cours, et il n'existe que trois sortes de billets de
banque, qui valent respectivement 57, 62 et 72 couronnes.
Hier, Audrey a acheté des croissants à la boulangerie, qui lui ont coûté
4 couronnes. Elle a donné un certain nombre de billets, d'un montant
inférieur à 600 couronnes, et le vendeur a pu lui rendre la monnaie
exacte de son achat.
Quelle somme Audrey a-t-elle donnée au vendeur?
Vous devez écrire un code Python qui résout cet exercice. C'est un exo pour débutants, ça utilise des boucles, des instructions if, éventuellement des fonctions.
edit:Ce code est faux et donne le bon résultat par chance.
def syldave(n, limit, billets):
prv, crt = [n], []
while min(prv) < limit:
for p in prv:
for b in billets:
crt.append(p + b)
for montant in crt:
for b in billets:
if montant % b == 0:
return montant
prv, crt = crt[0:], []
return -1
billets = (57, 62, 72)
print syldave(4, 600, billets)
Sinon je trouve bien la valeur que tu obtiens mais j'en obtiens aussi une autre ce qui m'étonne parce que l'énoncé laisse penser qu'il n'y a qu'un seul montant à trouver. Ce montant est 580=8A+2B=4+8C
def syldavie(lim):
a = 57
b = 62
c = 72
for i in range(0,lim):
for j in range(0,lim):
for k in range(0,lim):
for m in range(0,lim):
for n in range(0,lim):
for l in range(0,lim):
if ((i-m)*c+(j-n)*b+(k-l)*a) == 4:
return ((i,j,k),(m,n,l))
print syldavie(10)
Inkamath on GitHub - Interpréteur d'expressions mathématiques. Reprise du développement en cours.
def syldavie(lim):
a = 57
b = 62
c = 72
for i in range(0,lim):
for j in range(0,lim):
for k in range(0,lim):
for m in range(0,lim):
for n in range(0,lim):
for l in range(0,lim):
if ((i-m)*c+(j-n)*b+(k-l)*a) == 4:
return ((i,j,k),(m,n,l))
print syldavie(10)
Il suffit en fait de passer la limite à 10 billets :
def syldavie(lim):
a = 57
b = 62
c = 72
ret = []
val = []
for i in range(0,lim):
for j in range(0,lim):
for k in range(0,lim):
for m in range(0,lim):
for n in range(0,lim):
for l in range(0,lim):
if ((i-m)*a+(j-n)*b+(k-l)*c) == 4:
ret.append(((i,j,k),(m,n,l)))
val.append(i*a+j*b+k*c)
mini = min(val)
return (mini, ret[val.index(mini)])
print syldavie(11)
Inkamath on GitHub - Interpréteur d'expressions mathématiques. Reprise du développement en cours.
>>> for i in range(0, 601, 57):
for j in range(0, 601, 62):
for k in range(0, 601, 72):
somme=i+j+k+4
if somme<600 and (somme%57==0 or somme%62==0 or somme%72==0): print somme
Le but n'étant pas de faire une forme généralisée n'est-ce pas?
Rien ne dit que la monnaie est donnée avec une seule catégorie de billets. J'ai peut-être mal compris ton code mais j'ai l'impression qu'il présuppose une connaissance de la solution (le fait que Audrey paye avec un seul type de billets).
Au passage j'en profite pour signaler que je n'ai toujours rien compris à la solution de GurneyH
Inkamath on GitHub - Interpréteur d'expressions mathématiques. Reprise du développement en cours.
Au passage j'en profite pour signaler que je n'ai toujours rien compris à la solution de GurneyH
Je pars de la valeur 4, je construit les valeurs suivantes possibles en ajoutant chaque type de billet à 4
[4]
->[61, 66, 76]
je répète l'opération en partant de cette liste
[66, 66, 76]
->[118, 123, 133, 123, 128, 138, 133, 138, 148]
et ainsi de suite jusque qu'à ce qu'une valeur de la liste soit un multiple d'un des billets.
Si j'étais plus à l'aise en python, j'aurais probablement utilisé un dictionnaire.
Rien ne dit que la monnaie est donnée avec une seule catégorie de billets. J'ai peut-être mal compris ton code mais j'ai l'impression qu'il présuppose une connaissance de la solution (le fait que Audrey paye avec un seul type de billets).
execute ceci et dis moi si tu ne vois pas toutes les catégories
>>> for i in range(0, 601, 57):
for j in range(0, 601, 62):
for k in range(0, 601, 72):
somme=i+j+k+4
if somme<600 : print somme
Ca je le sais c'est juste pour t'indiquer que sur une somme maxi, tu as toutes les combinaisons entre toutes les catégories.
Maintenant le programme correct se trouve dans mon 1er post
Pour des croissants à 12 couronnes et billets (57, 62 et 72):
0 billets de 57, 0 billets de 62, 3 billets de 72, 228 est la somme totale recherchee.
0 billets de 57, 0 billets de 62, 5 billets de 72, 372 est la somme totale recherchee.
0 billets de 57, 1 billets de 62, 5 billets de 72, 434 est la somme totale recherchee.
0 billets de 57, 2 billets de 62, 5 billets de 72, 496 est la somme totale recherchee.
0 billets de 57, 3 billets de 62, 2 billets de 72, 342 est la somme totale recherchee.
0 billets de 57, 3 billets de 62, 5 billets de 72, 558 est la somme totale recherchee.
0 billets de 57, 6 billets de 62, 1 billets de 72, 456 est la somme totale recherchee.
0 billets de 57, 9 billets de 62, 0 billets de 72, 570 est la somme totale recherchee.
1 billets de 57, 0 billets de 62, 3 billets de 72, 285 est la somme totale recherchee.
1 billets de 57, 3 billets de 62, 2 billets de 72, 399 est la somme totale recherchee.
1 billets de 57, 6 billets de 62, 1 billets de 72, 513 est la somme totale recherchee.
2 billets de 57, 0 billets de 62, 3 billets de 72, 342 est la somme totale recherchee.
2 billets de 57, 0 billets de 62, 6 billets de 72, 558 est la somme totale recherchee.
2 billets de 57, 3 billets de 62, 2 billets de 72, 456 est la somme totale recherchee.
2 billets de 57, 6 billets de 62, 1 billets de 72, 570 est la somme totale recherchee.
3 billets de 57, 0 billets de 62, 3 billets de 72, 399 est la somme totale recherchee.
3 billets de 57, 3 billets de 62, 2 billets de 72, 513 est la somme totale recherchee.
4 billets de 57, 0 billets de 62, 3 billets de 72, 456 est la somme totale recherchee.
4 billets de 57, 3 billets de 62, 2 billets de 72, 570 est la somme totale recherchee.
5 billets de 57, 0 billets de 62, 3 billets de 72, 513 est la somme totale recherchee.
6 billets de 57, 0 billets de 62, 3 billets de 72, 570 est la somme totale recherchee.
Ah d'accord, mais ca j'avais vu... Le problème se situe au niveau du test. Rechercher un reste nul de la somme par l'une des catégorie de billet revient à dire :
- Audrey payera avec une seule catégorie de billet (cas 1)
OU (j'insiste sur le ou)
- Le commerçant rendra la monnaie dans une seule catégorie de billet (cas 2)
Pour illustrer mon propos voici la solution donnée par mon programme :
(570, ((10, 0, 0), (0, 1, 7)))
Audrey donne 10 billets de 57 et le commerçant rend 1 billet de 62 et 7 de 72 (cas 1).
La question que je me pose est de savoir si ton programme et celui de GurneyH trouveraient la solution si celle-ci ne tombait dans le cas 1 ou 2.
Attention, je ne dis pas que vos programmes sont faux. J'essaye simplement de comprendre pourquoi ça marche.
Inkamath on GitHub - Interpréteur d'expressions mathématiques. Reprise du développement en cours.
J'ai refait le code avec un dictionnaire et en affichant les étapes.
edit: même problème que mon code précédent, cad faux.
def syldave(n, limit, billets):
prv, crt = {4 : True}, {}
while min(prv) < limit:
for p in prv:
for b in billets:
if p + b not in crt:
crt[p + b] = True
print [k for k in crt]
for montant in crt:
for b in billets:
if montant % b == 0:
return montant
prv, crt = crt, {}
return -1
billets = (57, 62, 72)
print syldave(4, 600, billets)
La solution naïve s'exprime aussi très aisément de manière fonctionnelle avec les compréhensions de listes:
vals = [x+y+z for x in xrange(0,600,62) for y in xrange(0,600,57)\
for z in xrange(0,600,72) if x+y+z<600]
sols = [x for x in vals for r in vals if x-4==r]
print sols # [570, 580]
C'est quand même plus clair; on procède en deux étapes : on génère la liste de toutes les valeurs inférieurs à 600 qu'on peut obtenir avec les trois billets.
Ensuite on relève chaque élément qui fait partie de cette liste tel qu'il en existe un autre inférieur de 4 couronnes.
La solution naïve s'exprime aussi très aisément de manière fonctionnelle avec les compréhensions de listes:
vals = [x+y+z for x in xrange(0,600,62) for y in xrange(0,600,57)\
for z in xrange(0,600,72) if x+y+z<600]
sols = [x for x in vals for r in vals if x-4==r]
print sols # [570, 580]
C'est vrai que les listes en compréhension (traitées dans le tuto) permettent une solution plus concise qu'avec des instructions for/if (bien que les expressions aient alors tendance à tenir sur plusieurs lignes comme c'est le cas ici ce qui nuit un peu à la lisibilité car la rupture de ligne n'est pas syntaxique). Toutefois, et si je me fie à mes souvenirs, les emboitements de for ainsi que le if ne me semblent pas si simples à appréhender pour un débutant. La seule chose qui me gêne (disons que c'est pas très joli) dans ton code c'est que tu évalues 2 fois x+y+z. Sinon, un dictionnaire sera plus efficace, en particulier pour trouver sols (recherche linéaire au lieu de quadratique dans ton cas) et sans compter que ça évite les doublons dans vals.
Du point de vue mémoire ça allège, du point de vue exécution, pas sûr.
Mon code était comme ceci :
A,B,C,M=57,62,72,600
r=[]
for x in range(M//A+1):
for y in range(M//B+1):
for z in range(M//C+1):
m=x*A+y*B+z*C
if 0<m<=M:
r+=[m]
for m in r:
if m-4 in r:
print (m)
En tout cas, pas besoin d'antislash pour séparer en 2 lignes une list comprehension. Et finalement, même avec coupure juste avant le for, ça reste plus agréable à lire qu'une boucle for, moins naturelle.
mouais, une fois de plus, on est dans le domaine du subjectif. Une succession de for dans une expression peut être troublante pour une certaine catégorie de personnes qui apprennent Python, d'autant que ça se termine par une expression if, ça peut faire beaucoup pour certains.
Oui, mais dire "la liste des éléments de tel ensemble qui satisfont telle loi" est humainement plus clair que "je crée un ensemble vide, je parcours les éléments du premiers, s'ils vérifient la loi je les ajoute dans l'ensemble de départ", qui nécessite un certain effort intellectuel.
Alors oui, il faut connaître la syntaxe. Mais difficile aussi de comprendre une boucle for sans connaître sa syntaxe.
Et, euh, dans les deux cas il y a une succession de for, avec un if à la fin. Donc bon, argument en carton. La seule différence est qu'un cas décrit exactement la solution obtenue, alors que l'autre décrit les opérations nécessaires pour l'obtenir, ce qui nécessite encore une fois un effort (minime certes au bout d'un certain temps) de réflexion.
Candide, quand je vois ce qui te choque dans certaines formes Pythoniennes, je pense que c'est aussi parce que tu es aussi très habitué à une pratique rigoureuse du C.
Pour un débutant, je pense que les compréhensions de liste sont un outil puissant qu'il associe "assez facilement" au langage naturel (la liste des trucs faisant partie de tel ensemble et qui respectent telle condition), ou la liste des (trucs plus machin pour truc dans tel ensemble et pour machin dans tel autre ensemble, s'ils vérifient telle condition). Après, ce n'est évidemment que mon avis, mais de concevoir les compréhensions de liste de telle manière me permet de les utiliser de façon très naturelle. Cependant, c'est peut-être aussi mon côté matheux, puisque les compréhensions de liste sont finalement une traduction assez fidèle de la manière dont on écrit un ensemble en mathématiques : <math>\(\left\lbrace i \in \mathbb{N} | 2i < 50\right\rbrace\)</math>
Candide, quand je vois ce qui te choque dans certaines formes Pythoniennes, je pense que c'est aussi parce que tu es aussi très habitué à une pratique rigoureuse du C.
Non aucun rapport, ça ne me choque pas et il n'y a aucune incompatibilité entre le C et Python, je dirais même que dans beaucoup de situations, il y a potentialisation.
Citation : NoHaR
Pour un débutant, je pense que les compréhensions de liste sont un outil puissant qu'il associe "assez facilement" au langage naturel (la liste des trucs faisant partie de tel ensemble et qui respectent telle condition),
Oui, c'est ce je pense aussi. Seulement dans le cas qui nous intéresse, ce n'est pas une banale liste en compréhension, elle a deux particularités (for imbriqués + if terminal) qui font que ce n'est pas aussi aisé que [x**2 for x in range(10)].
Citation : NoHaR
les compréhensions de liste sont finalement une traduction assez fidèle de la manière dont on écrit un ensemble en mathématiques : <math>\(\left\lbrace i \in \mathbb{N} | 2i < 50\right\rbrace\)</math>
Oui, c'est ce je pense aussi. Seulement dans le cas qui nous intéresse, ce n'est pas une banale liste en compréhension, elle a deux particularités (for imbriqués + if terminal) qui font que ce n'est pas aussi aisé que [x**2 for x in range(10)].
Certes, mais la version impérative équivalente a aussi besoin de deux for et d'un if. Donc au final, on en revient exactement au même problème, avec toujours une solution plus descriptive et plus agréable avec des list comprehensions.
Voici ma solution pour cet exo. J'ai cherché à utiliser quelques notions nouvelles pour moi (groupby) :
from itertools import groupby
billets = (57,62,72)
l = []
# genere toutes les combinaisons possibles (stocke dans l)
def combinaisons(acc, pos):
for i in range(pos,len(billets)):
billet = billets[i]
n = sum(acc) + billet
if n < 600:
l.append((n, acc+[billet]))
combinaisons(acc+[billet], i)
combinaisons([], 0)
l.sort(key=lambda x: x[0])
# cree un dictionnaire avec les sommes possibles
# et les combinaisons de billets correspondants
d = {k:[ll[1] for ll in g] for k,g in groupby(l, key=lambda x: x[0])}
# cherche la/les solution/s
for elt in d:
if (elt+4) in d:
print(elt, ':', d[elt])
print(elt+4, ':', d[elt+4], '\n')
out = []
for a in range(600//57+1):
for b in range(600//62+1):
for c in range(600//72+1):
if a*57+b*62+c*72<600: out.append(a*57+b*62+c*72)
out = sorted(set(out))
for e,i in enumerate(out,1):
if i+4 in out[e:]: break
print i+4
Python c'est bon, mangez-en.
Monnaie syldave
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
Python c'est bon, mangez-en.