Bibm@th

Forum de mathématiques - Bibm@th.net

Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...

Vous n'êtes pas identifié(e).

#1 08-02-2020 15:15:12

Cédrix
Membre
Inscription : 15-08-2019
Messages : 77

algo billets de banque avec Python

Bonjour,
un DAB propose de ne distribuer que des billets de 10 ou 20 euros.
Lors d'un retrait, le DAB distribue le moins de billets possibles.
Voici l'algorithme dans le livre :
def DAB(n) :
    if n%10!=0:
        return "impossible"
    else :
        i=0
        while n>=20:
            n,i=n-20,i+1
        billets_20=i
        billets_10=n//10
    return billets_10,billets_20
Je ne comprends pas la ligne n,i=n-20,i+1 et pourtant l'algorithme fonctionne (je viens de le tester !).
Si je prends un exemple : DAB(50).
Pour DAB(50), le reste de 50 par 10 est égal à 0 donc on est dans la boucle else :
tant que n est plus grand que 50, c'est le cas à la première étape,
n vaut 50, i vaut 50-20=30, i vaut 0+1 =1 (d'ailleurs pourquoi i ne serait pas plutôt égal à 30+1 car la valeur précédente de i était 30).
Ensuite billets de 20=1
billets de 10=5 qui est le quotient de 50 par 10.
étape 2 : on a toujours n = 50 ???
Je ne comprends pas ce qu'il se passe à la ligne n,i=n-20,i+1.
J'aurais plutôt mis n,n=n-20,i+1 ???
Merci de votre aide !
C.

Hors ligne

#2 08-02-2020 18:50:24

freddy
Membre chevronné
Lieu : Paris
Inscription : 27-03-2009
Messages : 7 457

Re : algo billets de banque avec Python

Salut,

non, non, je pense que tu lis mal l'instruction. Il faut la lire comme suit : $n = n-20$ ; $i=i+1$ qui compte le nombre de billet de 20 dans le montant $n$ demandé.
Donc l'instruction dit : décompte le nombre de fois que $n$ est composé de 20.

Faut faire attention, le code est très précis, yoshi t'en dira plus quand il aura un peu de temps.

Dernière modification par freddy (08-02-2020 19:47:20)


De la considération des obstacles vient l’échec, des moyens, la réussite.

Hors ligne

#3 08-02-2020 19:56:48

Maenwe
Membre confirmé
Inscription : 06-09-2019
Messages : 409

Re : algo billets de banque avec Python

Bonsoir,
Je suis tout à fait d'accord avec @freddy ! Quelques précisions :
@Cédrix tu as écrit que l'on reste dans la boucle tant que $n \geq 50$ mais ce n'est pas ce que dit cette portion de code, elle commence bien par "while n>=20:" ce qui veut exactement dire "tant que $n\geq 20$ exécuter ce qui suit et qui est indenté".
La ligne "n,i=n-20,i+1" peut se réécrire en deux lignes :
   n = n - 20
   i = i + 1
ça sert à attribuer des valeurs à plusieurs variable en une seule ligne. Ce qui est à gauche de la virgule et à gauche du signe égal (ici $n$) est égal à ce qui est à droite du signe égal et à gauche de la virgule (ici $n-20$).

En ce qui concerne l'interprétation de freddy, je pense qu'il est important d'écrire ceci sous forme de suites en ce qui concerne l'interprétation d'un code tel que celui-ci pour éviter des confusions du types (après tout dépend du niveau du programmeur je suppose ! J'ai peut-être aussi tendance à faire ça pour "gagner du temps") : puisque $n = n-20$ alors $-20 = 0$, je ne comprends pas, ça n'a pas de sens ! Donc pour une interprétation mathématiques de cette ligne "n,i=n-20,i+1" est $n_{k+1} = n_{k} - 20$ et $i_{k+1} = i_{k} + 1$.

Dernière modification par Maenwe (08-02-2020 20:08:55)

Hors ligne

#4 08-02-2020 20:01:46

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 16 948

Re : algo billets de banque avec Python

Bonsoir,

Me v'la...
L'algorithme est "ridicule"...
1er point.
La problématique étant distribuer le minimum de billets possibles, cela entraîne donc de distribuer un nombre maximum de billets de 20 €.
2e point
Toute valeur du retrait possible devant être un multiple de 10, cf l'instruction

if n%10 !=0:
    return "Impossible"

on en déduit la chose suivante :
soit n est un multiple de 20, soit c'est un multiple de 20, + 10.
Si n%=20, le nombre de billets de 20 est n//20,
Dans l'autre cas, il y a un billet de 10, et (n-10)//20 billets de 20...
Donc  la boucle while 'attention else: n'esqt pas une boucle et ne sert strictement à rien.
Reprenons.
On entre dans la fonction et on trouve :

    if n%10!=0:    
        return "impossible"
    else:

Question : pourquoi ce "else" ?
Réponse naïve : La condition if n%10!=0: peut être soit remplie, soit non. On a bien à faire à la structure :

Si condition:

Sinon:

Bin, oui et non...0%10=5
Je reçois "Impossible", d'accord.
Pourquoi ? Parce que nous sommes sortis de la fonction : le return a fait son office. Le script n'est pas allé plus loin...

Et si je passe 120, j'obtiens la réponse (0,6), et (1,6) pour 130.
Dans les deux cas n%10 == 0, la condition n'est pas vérifiée on passe au calcul.
Pourquoi ?
Réponse naïve : grâce au else !
Bin... ici, non ! Si j'indente correctement ce qui le suit, je peux supprimer le else :

def DAB(n) :
    if n%10!=0:    
        return "impossible"
    i=0
    while n>=20:
        n,i=n-20,i+1
        print(i,n)
    billets_20=i
    billets_10=n//10
    return billets_10,billets_20
   
print(DAB(150))

Testez donc : ça marche ! Pourquoi ?
Parce qu'ici
si la condition n'est pas vérifiée
   le return nous fait sortir de la fonction et interrompt son exécution,
si la condition est vérifiée,
   le return n'a pas exécuté (toutes les instructions entre le if et le return auraient été ignorées s'il y en avait eu)
   le script a enchaîné avec i=0.
   i est le nombre de billets de 20.
   Reprenons l'exemple de DAB(150).
   avec un print bien placé, tu peux voir le déroulement :
   1 130    1 billet de  20 donné,  reste à retirer 130
   2 110    2 billets de  20 donnés,  reste à retirer 110
   3  90     3 billets de  20 donnés,  reste à retirer 90
   4  70     4 billets de  20 donnés,  reste à retirer 70
   5  50     ........................................................
   6  30     ........................................................
   7  10     7 billets de  20 donnés,  reste à retirer 10 --> sortie de boucle puisque n<20
S'affiche alors 1 (billet de 10) obtenu en divisant n par 10 : 10//10 =1 et 7 (billet de 20) valeur de i...
  (1, 7)

La boucle Tant que n >= 20: (while) ne fait que répéter la manœuvre suivante :
je donne un billet de 20, reste à distribuer n-20 et je passe i (le nombre de billets de 20) à i+1 (au début 0+1=1)

Rien à rajouter à ce que dit freddy si ce n'est qu'on aurait pu écrire sur deux lignes (l'ordre) n'importe pas...
n=n-20
i=i+1
Si on veut être Pythonien, dans ce cas on peut écrire d'ailleurs
n-=20
i+=1

Maintenant compte tenu de mes commentaires, on obtient :

def DAB(n) :
    if n%10!=0:    
        return "impossible"
    billets_20=n//20
    billets_10= (n-20*billets_20)//10
    return billets_10,billets_20

print(DAB(140))
print(DAB(370))
 

Renvoie
(0,7)
(1,18)

J'avais fait un script autrement plus ch... après un France-Angleterre qui répondait à cette problématique :
étant un score de Rugby (par ex 44 - 31) trouver toutes les façons possibles d'arriver à 44 et 33
via :
Drop ou pénalité : 3
Essai non transformé : 5
Essai non transformé : 7

@+

[EDIT] Bravo à Maewe : bonne analyse...
Après réflexion, je suis trop dur avec l'Algo, c'était sûrement une volonté délibérée d'utiliser la structure if else et une boucle while.
Cela dit, il n'empêche que je trouve l'exemple utilisé pas très approprié...

Dernière modification par yoshi (08-02-2020 20:44:11)


Arx Tarpeia Capitoli proxima...

Hors ligne

#5 08-02-2020 22:18:04

freddy
Membre chevronné
Lieu : Paris
Inscription : 27-03-2009
Messages : 7 457

Re : algo billets de banque avec Python

Re,

j'avais bien imaginé travailler aussi avec les multiples, mais bon, en python, je n'y suis pas encore vraiment.
Sinon, ce serait marrant de refaire le truc avec des billets de 5, 10, 20 et 50 avec l'instruction de distribuer un nombre minimum de billet. Pas très compliqué, mais il devrait y avoir plus de code et donc faire un pgm avec un nombre minimal de ligne de code :-)


De la considération des obstacles vient l’échec, des moyens, la réussite.

Hors ligne

#6 09-02-2020 10:55:15

Cédrix
Membre
Inscription : 15-08-2019
Messages : 77

Re : algo billets de banque avec Python

Bonjour,
merci infiniment pour vos réponses et les prolongements hautement précis et rigoureux qui m'éclairent !
C.

Hors ligne

Pied de page des forums