Discussion :

[Invité]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[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

[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?

[Invité]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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?

[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! )

Des boucles de cheveux ! A ton avis ?

[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

[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..

[Invité]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[Invité]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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!

[plaxtor]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 !

[wiztricks]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[plxpy]

Bonjour

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[wiztricks]

Salut,

[*]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

[plaxtor]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 !

[wiztricks]

Salut,

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
On sort un peu de la traduction basique d'un algo. mathématique à un problème qui serait un peu plus "informatique".

- W

[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

[Invité]

J'ai vraiment besoin d'éclaircissement, je me sens tout niait d'un coup...

[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?

[plaxtor]

Si tu parles de cette ligne :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[plxpy]

... 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?

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.