Exercice python, je bloque !

Version imprimable

Salut à tous!
Mon professeur m'a demandé d'écrire un programme python, affichant les différentes manières d'obtenir 100 euros avec des billets de 10euros, de 5 euros et des pièces de 2 euros.

Cela fait une demi heure que j'essaye ne serait-ce que d'écrire un premier jet, mais je bloque vraiment..

voici mes premiers jets, mais ça n'avance pas :/
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 a=2 b=5 c=10 x=0 e=0 f=0 g=0 while(x!=100): x=a*e e=e+1 if(x==100): print("100=",a,"*",e-1) x=0 while(x!=100): x=b*f f=f+1 if(x==100): print("100=",b,"*",f-1) x=0 while(x!=100): x=c*g g=g+1 if(x==100): print("100=",c,"*",g-1) x=0 c=0 g=0 f=0 while(x!=100): x=c*g+b*f g=g-1 f=f+1 if(x==100): print("100=",c,"*",g,"+",b,"*",f) x=0

11/01/2015, 23h29
plaxtor

Bonjour! Pour éditer du code tu as les balises de code (le dièse ou hashtag pour les jeunes :) )en haut quand tu édites ton message !
Une idée : tu fais trois boucles imbriquées qui parcourent les multiples de 10, 5 et 2 et tu incrémentes si la somme de tes 3 indices vaut 1 :)

Une autre idée si tu aimes les maths et pas trop la programmation :

Tu cherches le 100è terme de l'expression 1/(1-X**2) * 1/(1-X**5) * 1/(1 - X**10) développée en série de taylor ( ou de la série formelle associée si tu veux pas te soucier de convergence )
Ca te donne tous les 10i + 5j + 2k = 100 ! avec i,j,k dans N. L'expression sera horrible mais le résultat juste

Bonne chance :D
11/01/2015, 23h37
Invité

Je n'ai pas compris l'équation de taylor xD
Seulement 3 boucles imbriquées suffisent ?? J'aurai les 66 solutions? Des boucles IF ou While?

Code:

1
2
3
4
5
6
7
8
9
10
11
12
while(x!=100):
    x=10*i+5*j+2*k
    i=i+1
    while(x!=100):
        x=10*i+5*j+2*k
        j=j+1
        while(x!=100):
            x=10*i+5*j+2*k
            k=k+1
        x=0
    x=0
x=0

Mmmmmh, je progresse?

11/01/2015, 23h56
plaxtor

Laisse tomber c'est hardcore dans mon exemple ! Mais si tu as un algorithme pour la division euclidienne de polynôme en puissance croissante ça devient facile (en gros)
Pour faire simple :
1/(1-X) = (1+X+X^2 + X^3 + .... )
Et 1/(1-X^k) = (1 + X^k + X^2k + ...)
Par produit des trois facteurs, le 100è terme en X vaudra ce que tu cherches (faut aimer les maths hein! :D)

Des boucles de cheveux ! A ton avis ? :)
12/01/2015, 00h01
plaxtor

Tu as un indice pour les multiple de 10, de 5 et de 2 ! (i varie entre 0 et 10, j entre 0 et 20 et k entre 0 et 50)
Donc 3 boucles whiles imbriquées.
Et dans la dernière boucle tu testes si tu as bien 10*i + 5*j + 2*k = 100
12/01/2015, 00h03
Invité

Je ne pense pas avoir le niveau en maths pour réaliser cela, mais si tu as deux trois liens pour que j'apprenne cette équation, ça me plairait pas mal!

Mmmmh, je pense que je vais arrêter de chercher, j'y ai passer l'après-midi..

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
i=0
j=0
k=0
x=0
 
while(i<10):
    x=10*i + 5*j + 2*k
    i=i+1
    if(x==100):
        print("100=",10,"*",i,"+",5,"*",j,"+",2,"*",k)
        x=0
        while(j<20):
            x=10*i + 5*j + 2*k
            j=j+1
            if(x==100):
                print("100=",10,"*",i,"+",5,"*",j,"+",2,"*",k)
                x=0
                while(k<50):
                    x=10*i + 5*j + 2*k
                    k=k+1
                    if(x==100):
                        print("100=",10,"*",i,"+",5,"*",j,"+",2,"*",k)
                        x=0

Le programme ne m'affiche rien

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
i=0
j=0
k=0
x=0
 
while(i<11):
    x=10*i + 5*j + 2*k
    i=i+1
    if(x==100):
        print("100=",10,"*",i-1,"+",5,"*",j,"+",2,"*",k)
        x=0
        i=0
        while(j<21):
            x=10*i + 5*j + 2*k
            j=j+1
            if(x==100):
                print("100=",10,"*",i,"+",5,"*",j-1,"+",2,"*",k)
                x=0
                j=0
                while(k<51):
                    x=10*i + 5*j + 2*k
                    k=k+1
                    if(x==100):
                        print("100=",10,"*",i,"+",5,"*",j,"+",2,"*",k-1)
                        x=0

Reusltats:
100= 10 * 10 + 5 * 0 + 2 * 0
100= 10 * 0 + 5 * 20 + 2 * 0
100= 10 * 0 + 5 * 0 + 2 * 50

Il m'en manque encore 63... Je désespère!

Il te suffit de savoir faire un produit de cauchy sur deux polynôme c'est tout ! En manipulant les sommes tu démontres le résultat !
Sinon tu à l'air de t’emmêler dans ton code, ça devrait donner quelque chose comme :
Code:

1 2 3 4 5 6 7 8 9 10 11 i = j = k = x = 0 while i<=10: while j<=20: while k<=50: if 10*i + 5*j + 2*k == 100: x += 1 k += 1 j += 1 i += 1 print(x)
Essaye de lire et de comprendre le code, comprendre comment il marche. x représente le nombre de possibilités ! Si tu as bien compris tu peux essayer avec des boucles for, en utilisant la fonction
range ! :)

Salut,

Se lancer dans le code sans avoir une idée de comment dérouler l'algo. sur le papier est une très mauvaise idée car vous allez y passer un temps déraisonnable avec peu de chance d'obtenir un résultat satisfaisant.

C'est pas si compliqué de commencer par écrire "trouver tous les entiers (x, y, z) positifs tels que 10 * x + 5 * y + 2 * z = 100".

Si vous regardez ce qu'il se passe lorsque x ou y ou z valent 0, on a les solutions (10, 0, 0), (0, 20, 0), (0, 0, 50).
On peut aussi remarquer que si x = 9, alors y pourra prendre les valeurs 0, 1, 2 et que z sera égal à (100 - (10 * x + 5 * y)) / 2.
Avec x = 8, y pourra varier de 0 à (100 - (10 * x)) / 5, et z sera toujours donné par (100 - (10 * x + 5 * y)) / 2.

On peut traduire çà en Python:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 >>> x = 10 >>> while x >= 0: ... y_max = (100 - 10 * x) / 5 ... y = 0 ... while y <= y_max: ... z = (100 - (10*x + 5*y)) / 2 ... print (x, y, z, 10*x + 5*y + 2*z) ... y = y + 1 ... x = x - 1 ... (10, 0, 0, 100) (9, 0, 5, 100) (9, 1, 2, 99) ....
Ca buggue car çà sort (0, 1, 47, 99) i.e. j'ai été optimiste en écrivant "z sera toujours donné par (100 - (10 * x + 5 * y)) / 2".
Il serait moins faux de s'assurer de la condition (100 - (10 * x + 5 * y)) est divisible par 2.
On s'assure aussi qu'on n'a pas fait la même gaffe côté 5...
Puis le souci sera de traduire la condition "(100 - (10 * x + 5 * y)) est divisible par 2": l'important étant de savoir ce qu'on veut "avant" d'essayer de le traduire en code.
On peut utiliser l'opérateur '%' mais comme on aura aussi besoin du quotient dans certains cas, on peut préférer divmod.
Le nouveau code:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 >>> x = 10 >>> count = 0 >>> while x >= 0: ... y_max = (100 - 10 * x) / 5 ... y = 0 ... while y <= y_max: ... if (100 - (10*x + 5*y)) % 2 == 0: ... z = (100 - (10*x + 5*y)) / 2 ... print (x, y, z, 10*x + 5*y + 2*z) ... count = count + 1 ... y = y + 1 ... x = x - 1 ... (10, 0, 0, 100) (9, 0, 5, 100) (9, 2, 0, 100) (8, 0, 10, 100) (8, 2, 5, 100) ... (0, 14, 15, 100) (0, 16, 10, 100) (0, 18, 5, 100) (0, 20, 0, 100) >>> count 66
- W

Bonjour
Citation:
Envoyé par plaxtor
Code:

1 2 3 4 5 6 7 8 9 10 i = j = k = x = 0 while i<=10: while j<=20: while k<=50: if 10*i + 5*j + 2*k == 100: x += 1 k += 1 j += 1 i += 1 print(x)
Argggh ! à l'essai, ça donne 1 seule solution : 50 pièces de 2 Euros

L'initialisation des compteurs, faite en une seule fois au début, est foireuse ! Quand on arrive en butée dans un while imbriqué, qu'on ne touche pas au compteur et qu'on remet ça, on ne passe même plus dans la boucle.

Avec un nombre d'itérations moins important pour ne pas avoir des tas d'affichage, on voit très bien ce qui se passe :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 >>> i = j = k = 0 >>> while i<=2: ... print("iteration i avec %d" % i) ... while j<=2: ... print("\titeration j avec %d" % j) ... while k<=2: ... print("\t\titeration k avec %d" % k) ... k += 1 ... j += 1 ... i+= 1 ... iteration i avec 0 iteration j avec 0 iteration k avec 0 iteration k avec 1 iteration k avec 2 iteration j avec 1 iteration j avec 2 iteration i avec 1 iteration i avec 2 >>>
Sinon, deux remarques :

vraiment pas pythonique ... mais (la remarque avait été faite dernièrement par wiztricks sur un exercice du Swinnen - je n'ai pas retrouvé le post), je suppose qu'ici, Python est utilisé pour apprendre les rudiments de la programmation et donc, au départ, on fait du python à la sauce C pour apprendre à faire des boucles "à la main"
cependant, surtout quand on patauge un peu dans les compteurs et les variables, la lisibilité y gagnerait en utilisant des noms de variables de plus d'un caractère !!! vingt qui contiendrait le nombre de billets de 20 plutôt que i, cinq plutôt que j, etc...

EDIT : posté sans avoir vu la réponse précédente de wiztricks

12/01/2015, 11h10
wiztricks

Salut,

Citation:

Envoyé par plxpy

[*]vraiment pas pythonique ... mais (la remarque avait été faite dernièrement par wiztricks sur un exercice du Swinnen - je n'ai pas retrouvé le post), je suppose qu'ici, Python est utilisé pour apprendre les rudiments de la programmation et donc, au départ, on fait du python à la sauce C pour apprendre à faire des boucles "à la main"

Le soucis est que dans l'apprentissage de la programmation, dérouler sa boucle pas à pas en gérant les indices à la mano. reste plus proche de l'algorithme qu'on est supposé avoir fait fonctionner sur le papier avant d'essayer de le traduire en code.
Le pythoniste dira que çà ressemble plutôt à du C mais en fait ce sont des babillages d'apprenti programmeur.
"range" est une abstraction utile lorsqu'on est un peu blasé d'avoir à taper l'initialisation, le test, l'incrémentation,... et qu'on en a marre de se faire prendre par ses oublis ou le placement d'une instruction dans le mauvais block car n'importe quel changement oblige à faire attention à 3 lignes de code parfois éloignées. "range" pose beaucoup moins de soucis.

- W

Arg l'erreur bête ! J'avais fait le truc avec des range mais l'auteur à choisit l'option while j'ai voulu respecter son choix de programmation et j'ai mal traduit ! Ça donne donc :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 x = 0 i = 0 #Représente ne nb de billets de 10 while i<=10: j = 0 # De billets de 5 while j<=20: k = 0 #De billets de 2 while k<=50: if 10*i + 5*j + 2*k == 100: x += 1 k += 1 j += 1 i += 1 print(x)
Comme il a été souligné, on peut utiliser la fonction range mais bon de mon point de vue on peut passer au range quand on maitrise le while, étant donné que le while est la boucle DE BASE.
De plus il est évident ici qu'on peut faire des simplifications. Par exemple le nombre de billet de 5 est pair (logique), on a également des majorations évidentes à faire, et la dernière boucle est limite inutile.

D'un autre côté on demande d'écrire un programme qui répond à la solution, sans vraiment se soucier de rapidité ou autre et la méthode ci dessus est la plus basique que l'on puisse imaginer.
Le mec bon en math il résout ça tranquille à la main (on oublie taylor hein! :) ) avec les équations diophantiennes, ça prend même pas 10mn.
De l'autre coté le mec qui est pas bon en math il risque de patauger s'il cherche des simplifications et au final il va perdre du temps et risque de se tromper pour rien, alors qu'un programme évident était à sa portée. Faut pas être manichéen non plus mais bon..

C'est un point de vue mais je pense qu'il faut déjà avoir un code de base en tête voir s'il marche, ET ensuite l'améliorer plutôt que de tout vouloir faire d'un coup. Du moins pour ceux qui ne sont pas à l'aise.
C'est discutable bien sur !

12/01/2015, 19h12
wiztricks

Salut,

Citation:

Envoyé par plaxtor

Le mec bon en math il résout ça tranquille à la main (on oublie taylor hein! :) ) avec les équations diophantiennes, ça prend même pas 10mn.

Traduire ce qu'on fait à la main en code avec des boucles "while" est une première étape incontournable.

Maintenant, imaginons que le nombre et la valeur de nos pieces soient saisies par l'utilisateur au début du programme.
Une fois ce pourrait être (10, 5, 2), le coup suivant (20, 9, 3, 1),...

Difficile de s'en sortir avec des "while" imbriqués :mouarf:
On sort un peu de la traduction basique d'un algo. mathématique à un problème qui serait un peu plus "informatique".

- W
12/01/2015, 19h31
Invité

Merci beaucoup PLXPY, mais pourriez vous m'expliquez les équations que vous utilisez dans votre algo, j'ai encore du mal à comprendre comment vous avez fait pour aboutir votre raisonnement... :S
12/01/2015, 19h36
Invité

J'ai vraiment besoin d'éclaircissement, je me sens tout niait d'un coup...
12/01/2015, 19h55
Invité

Désolé pour le triple poste, mais finalement il me faudrait seulement une explication à la ligne du IF, Si je comprend bien, Si l'équation n'est pas modulo 2, on n'écrit pas la solution? Et pourquoi donc?
12/01/2015, 20h37
plaxtor
Si tu parles de cette ligne :
Code:

1 2 if (100 - (10*x + 5*y)) % 2 == 0:
Elle est là pour vérifier que 100 - 10*x + 5*y est divisible par deux. En effet si elle ne l'était pas etant donné que tu cherches :
10*x + 5*y + 2*z = 100 avec x, y, et z dans N !!!!!
donc z = (100 - (10*x + 5*y))/2 Mais faut bien que ça fasse un entier on est d'accord ! C'est pour cela qu'il vérifie :)
12/01/2015, 20h38
plxpy

Citation:

Envoyé par valtomir

... finalement il me faudrait seulement une explication à la ligne du IF, Si je comprend bien, Si l'équation n'est pas modulo 2, on n'écrit pas la solution? Et pourquoi donc?

8O ké modulo ???

Le seul "if" correspond à "SI la somme des billets de 10 et 5 et des pièces de 2 vaut 100"

Dans le code proposé par plaxtor, on ne fait que compter les solutions possibles (qu'on mémorise dans la variable x). Si tu veux mémoriser/emmagasiner les solutions, utilise une liste

EDIT: OK, le modulo dans le code de wiztricks. Il y a des bouts de code un peu partout. C'est déjà dur, essaye de citer (écrire !) de quoi tu causes en recopiant les bouts de code.

hello,

pour résoudre le problème on peut aussi utiliser une fonction récursive comme ceci par exemple :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 def calcCombi(combi, elements, maxi, somme, cible): # on regarde si on a atteint la cible if somme == cible: affichage(combi, elements) return # on a dépassé if somme > cible: return for valeur in elements: if valeur >= maxi: # on copie la liste, puis on ajoute la valeur courante. copie = combi[:] copie.append(valeur) # Recursivement on ajoute plus de combinaisons. calcCombi(copie, elements, valeur, somme + valeur, cible) def affichage(combi, elements): global nb # on affiche une solution , nb = nb + 1 for element in elements: count = combi.count(element) print(count," x ",element, "€ - ", end="") print ("") # liste de combinaison de pièces et de billets combi = [] # billets ou pièces dont on dispose elements = [2, 5, 10] # variable globale du nombre de possibilités nb = 0 # départ. calcCombi(combi, elements, 0, 0, 100) print ("nombre de possibilités : ",nb)
Pour qu'une fonction récursive fonctionne, il faut une condition d'arrêt de la récursion. Ici c'est quand on atteint ou dépasse la cible. En python, il y a une profondeur max de récursion (à cause de la taille de la pile) c'est 1000 par défaut. On peut augmenter cette valeur par :
Code:

1 2 import sys sys.setrecursionlimit(x)
La fonction calcCombi dans l'exemple est appelée 2671 fois.
La profondeur max de récursion atteinte ici est de 50 ( cas où l'on utilise que des pièces à 2 euros)

Ami calmant, J.P