Discussion :

[desatan]

Bonjour,

Je cherche à créer sous python un algorithme permettant de donner les n combinaisons pour arriver à un nombre entier à partir de trois valeurs :
50, 20 et 10.

Par exemple, si je tape 50, l'algorithme doit me donner toutes les possibilités d'arriver à 50 avec mes trois valeurs :
50 ou 2 fois 20 + 10 ou 1 fois 20 + 3 fois 10 ou 5 fois dix etc.
Si je saisis 100, l’algorithme devra me donner toutes les combinaisons possible :
2 fois 50 ou 4 fois 20+ 2 fois 10 etc..

J'ai commencé un bout de code mais cela ne fonctionne pas.

Pouvez-vous m'aider s'il vous plait ?

Merci par avance.

Code :

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

1
2
3
4
5
6
7
8
9
10
sommeVoulue=int(input("Donner la somme voulue: "))
somme=sommeVoulue # on utilise une variable somme qui va stocker au fur et à mesure
cinquante=somme//50 #la somme restante après utilisation des billets
somme=somme%50
vingt=somme//20
somme=somme%20
dix=somme//10
somme=somme%10
print("pour la somme de %i euros, il faut : %i billets de 50, "%(sommeVoulue,cinquante),end=" ")
print("%i billets de 20, %i billets de 10," %(vingt,dix),end=" ")

[wiztricks]

Je cherche à créer sous python un algorithme permettant de donner les n combinaisons pour arriver à un nombre entier à partir de trois valeurs :
50, 20 et 10.

Ca serait mieux d'avoir un algorithme que l'on code avec Python!

Par exemple, si je tape 50, l'algorithme doit me donner toutes les possibilités d'arriver à 50 avec mes trois valeurs :
50 ou 2 fois 20 + 10 ou 1 fois 20 + 3 fois 10 ou 5 fois dix etc.
Si je saisis 100, l’algorithme devra me donner toutes les combinaisons possible :
2 fois 50 ou 4 fois 20+ 2 fois 10 etc..

Pour fabriquer un algorithme, on commence par le décrire sur une feuille de papier.
Dans votre cas, il s'agit de prendre un nombre N divisible par .... et trouver les différents (x, y, z) positifs ou nuls tels que N = 50*x + 20*y + 10*z.
Puis vous prenez un exemple si 50 s'écrit facilement (1, 0, 0) comment vous trouvez (0, 2, 1)?

- W

[desatan]

Ca serait mieux d'avoir un algorithme que l'on code avec Python!



Pour fabriquer un algorithme, on commence par le décrire sur une feuille de papier.
Dans votre cas, il s'agit de prendre un nombre N divisible par .... et trouver les différents (x, y, z) positifs ou nuls tels que N = 50*x + 20*y + 10*z.
Puis vous prenez un exemple si 50 s'écrit facilement (1, 0, 0) comment vous trouvez (0, 2, 1)?

- W

Merci.
Puis vous prenez un exemple si 50 s'écrit facilement (1, 0, 0) comment vous trouvez (0, 2, 1)?
Dans votre exemple (1,0,0) le 1 correspond à 50 et dans votre (0, 2, 1), le 2 correspond à 20 et le 1 à 10. L'algorithme doit aussi me donner : (0,1,3) et (0,0,5)

Mais je ne vois pas où vous voulez aller ? Je pense qu'effectivement, c'est un problème d'algorithme avant tout.

Faut il utiliser la récursivité ?

Encore merci

[wiztricks]

Vous prenez un exemple si 50 s'écrit facilement (1, 0, 0) comment vous trouvez (0, 2, 1)?

Parce que si j'ai un 50 de moins, il faut le ré-écrire avec des 20 et des 10 puisque N ne change pas.
Donc je peux commencer par trouver le nombre y de 20 qu'il y a dans 50, et je sais que z sera fonction du reste.
Puis à l'itération suivante, je diminue y d'une unité, et je recalcule z en fonction du nouveau reste.
Et lorsque y (et x) seront nuls, j'aurais fini avec (0, 0, 5).

Tout le boulot à faire sur la feuille de papier et son crayon est de détailler les étapes pour aboutir, in fine, à décrire un algorithme dont on pourra démontrer facilement que:

• il se termine,
• il trouve bien toutes les solutions,

qu'on pourra traduire/coder avec Python.

Je pense qu'effectivement, c'est un problème d'algorithme avant tout.

voilà.

Faut il utiliser la récursivité ?

Si à la sortie de l'étude de votre algorithme sur feuille de papier vous sortez avec un algorithme récursif, vous pourrez le coder avec une fonction récursive.
Mais pour l'instant, vous n'avez pas d'algorithme.... et la feuille de papier sur laquelle gribouiller pour le définir est toujours blanche...

- W

[desatan]

Merci.

Je ne comprends votre phrase : Et lorsque y (et x) seront nuls, j'aurais fini avec (0, 0, 3).

Si on reprend, 3 valeurs connues, 50, 20 et 10.

50 est x, 20 est y et 10 est z

Dans l'exemple où N=50, on doit avoir :

50=1x ou
50=0x+2y+1z ou
50=0x+1y+3z ou
50=0x+0y+5z

Je ne vois comment on peut avoir (0,0,3) ?

[wiztricks]

Je ne vois comment on peut avoir (0,0,3) ?

J'ai oublié de me relire... et vous aussi en écrivant 50=0x+1y+4z.
Voilà c'est corrigé.

Mais c'est pas en vous braquant sur ce genre de détails (importants mais bon.. que vous allez avancer côté algorithme.

- W

[wiztricks]

Tu es en train de refaire le jeu "le compte est bon". Ca peut se résoudre de façon générale (donc avec 3 ou 300 valeurs) en récursif de la façon suivante

On est plutôt en train de calculer les différentes façons de rendre la monnaie en fonction des billets qu'on a dans le tiroir caisse...

- W