Bonjour à tous,
quelqu'un a-t-il une idée de comment écrire un programme en Pascal, permettant à un monnayeur intelligent de proposer au client toutes les combinaison de pièces possible, sachant que le monnayeur prend des billet 5, 10 et 20€, et que les pièces pouvant etre rendu sont 20 et 50 ct, et 1 et 2€...
Une idée ou proposition?
Merci d'avance !
le cours d'informatique, c'est quel jour (afin qu'on puisse te répondre à temps pour ton devoir)
C'est pour un annale d'examen, ce n'est pas à faire obligatoirement.
Vous dites ça pour me faire comprendre que je n'ai pas posté au bon endroit ? Si oui, pouvez vous m'indiquer ou je peux poster...?
Pour étayer la réponse de wizz:
http://forums.futura-sciences.com/pr...ces-forum.html
Bonsoir,Envoyé par bilou51
Une idée : backtracking.
Ça fait un point de départ
Attention suivant la somme de départ le nombre de solutions peut vite devenir grand.
montre nous juste que tu as commencé à réfléchir, à établir une logique sur le problème, sur les différents cas possibles, sur les enchainements des évenements successifs (demandes) qui ne sont pas forcement identiques, etc...
ensuite, pour la programmation, ce sera d'une simplicité
ça viendra d'elle même
Je trouve le problème compliqué. Je pense qu'il faut deja tout convertir en centime. Après utiliser un repeat until je pense... Mais je ne vois pas comment faire. Je bloque completement...
Dans ce genre de problème, le bon sens prévaut. Comment ferais-tu si tu étais caissier et que tu devais rendre la monnaie? Tu convertirais la somme en centimes?
A+
Bon si ce problème est un peu compliqué, essaye de commencer avec un problème plus simple : au lieu de donner toute les possibilités de conversion peux-tu imaginer par exemple celle qui donne le moins de pièces ? celle qui donne le plus de pièces ?
Cela te permettra de te familiariser un peu avec le problème.
Ou plus simple, on essaie dans un premier temps de rendre le maximum de 20€, puis avec le reste de rendre le maximum de 10€, etc.
Ca je vois comment faire mais c'est le roulement que je ne vois pas comment organiser...
Comment t'aider?
Si tu es en master 2 d'info, je pense que tu vas finir par trouver
Si tu n'as jamais écrit une seule ligne de programme, je ne vois pas comment tu pourrais arriver à tes fins
Si tu es entre les 2, tu as dû voir ce qu'est une boucle.
Essaie de décomposer le problème comme si tu devais rendre toi-même la monnaie et tu vas bien voir ou se trouvent ces séquences répétitives.
salut
ben, c'est pas bien dur.
Dans un premier temps, tu remarques que la plus petite valeur disponible est de 20 centimes. Dés lors, il faut impérativement que la somme à rendre soit un multiple de 20.
1- Tu rends avec la valeur faciale la plus élevée possible ... tu soustrait... tu recommences... jusqu'à ce que tu soit obligé de choisir une valeur plus petite.
Alors, tu recommences à 1.
Le seul problème est de vérifier avant chaque opération, si la somme à rendre après l'opération en cours, reste divisible par 20.... sinon il faut éliminer une étape.
Par exemple : il reste 80 centimes à rendre. Pas question de rendre une pièce de 50 car après t'es cuit. Faut passer à 20 d'urgence.
Comme le souligne Jack ça va dépendre du niveau de ton examen ... ce genre d'exercice nécessite d'avoir vu et compris au minimum les tableaux, les enregistrements, la récursivité ...
En partant du principe que le monnayeur possède une réserve illimitée de pièces il faut se poser la question comment modéliser le problème. On peut voir le problème comme un tableau qui est le nombre de pièces distribuées [p20,p50,p100,p200] (p20 = nombre de pièces de 20 centimes ... p200 nombre de pièces de 2 euros), et d'une somme restant à compléter S, pour n'avoir que des entiers à manipuler j'exprime les sommes en centimes. Je note donc le problème ([p20,p50,p100,p200],S).
Par exemple une solution pour S=20 euros serait ([100,0,0,0],0) ou ([50,2,9,0],0) ou ([0,0,0,10],0), et ton problème de départ se note ([0,0,0,0],2000).
Donc en gros pour résoudre le problème ([p20,p50,p100,p200],S) il faut résoudre les sous problèmes ([p20 + 1,p50,p100,p200],S-20), ([p20,p50 + 1,p100,p200],S-50), ([p20,p50,p100 + 1,p200],S-100), ([p20,p50,p100,p200+1],S-200). Si on tombe sur un problème avec un S=0 on peut imprimer la solution, si on tombe sur un problème avec S<0 alors c'est infaisable on ne fait plus rien, et si S>0 alors on continue à chercher.
Tu as la récursivité, les conditions d'arrêts, le backtracking ... si ça te parle tu peux pouvoir donner l'algorithme je pense.
On n'a vu que les tableaux pour l'instant !
Bonjour,
C'est peut-être moi qui me trompe, mais j'ai l'impression que le "monnayeur" prend en entrée un billet (de 5, 10 ou 20 euros) et qu'il faut donner toutes les possibilités pour le changer en pièces.
En même temps, c'est un cas particulier du rendu de monnaie, ça ne change pas grand chose. C'est juste un peu plus simple.
Tu devrais y arriver tout de même, si tu as vu les boucles. Utiliser la récursivité (le fait qu'une fonction s'appelle elle-même), comme le propose Kwariz, simplifie l’algorithme, mais ce n'est pas indispensable (ça se démontre : il n'y a aucun algorithme qui impose une solution récursive).
En l’occurrence, en faisant une boucle sur le nombre de pièces de 2 euros, à l'intérieur de laquelle tu fais une boucle sur le nombre de pièces d'un euro, a l'intérieur de laquelle tu fais une boucle sur les pièces de 50 c ...
Ah ? Mais je ne vois pas système à mettre en places dans les boucles ? Quand on retire de pièce des 50 on ajoute une piece de 1? mais ça ne marche pas car 50 nest pas un multiple de 20ct...enfin je comprends pas... Je n'arrive pas à comprendre...
Bon sang, mais ça fait deux fois que je te demande comment tu ferais, toi, pour rendre la monnaie, dans le cas particulier de mon message#10 par exemple. essair de rédiger ceci en Français et tu ne seras pas loin de ton algo.
Une fois cette étape réussie, tu pourra embrayer dans le cas général qui t'es proposé.
Et bien j'ajoute les pieces jusqu'a ce que la somme des pieces soient la valeur du billet. Mais ce n'est pas le problème. Faire un combinaison, je sais faire. C'est le roulement pour avoir TOUTES les combinaisons.
Toutes les combinaisons possibles pour chaque type de billet (cela me paraît une demande délirante) ou la combinaison optimum pour chaque type de billet ? Peux-tu poster le texte intégral de l'énoncé ?
Rien ne sert de penser, il faut réfléchir avant - Pierre Dac
Le but de cette partie est d’écrire un programme Pascal qui simule un monnayeur de nouvelle
génération. Le monnayeur fonctionne de la manière suivante : le client entre un billet (billets acceptés
: 20 €, 10 € ou 5 €), le monnayeur doit afficher toutes les combinaisons possibles des pièces
disponibles (pièces qui peuvent être disponibles: 2 €, 1 €, 50 cent, 20 cent) et demande à l'utilisateur
de choisir quelle combinaison de pièces il souhaite avoir.
Le programme à réaliser devra prendre en entrée un nombre entier correspondant à la valeur du billet
entré par l'utilisateur et afficher à l’écran toutes les combinaisons possibles de pièces disponibles.
a) Génération des combinaisons de pièces: (3 points)
Ecrire la partie du programme qui lit la valeur du billet, puis calcule et affiche les combinaisons de
pièces valides.
Une combinaison valide contiendra au moins une pièce de 2 €, une pièce de 1 € et une pièce de 50
cent.
Par exemple, pour un billet de 5 €, une des combinaisons possibles s'affichera à l'écran de la
manière suivante :
Option 2 : 1 de 2 euros; 1 de 1 euro; 4 de 50 cent; 0 de 20 cent
b) Validité de la combinaison en fonction des pièces disponibles : (2 points)
Modifier la partie ci-dessus afin que la validité des combinaisons se fasse aussi en fonction des
pièces disponibles dans la machine.
On considérera dans ce programme que les nombres de pièces disponibles de chaque type sont des
constantes définies au départ.
A la fin, après l'affichage des combinaisons possibles, le programme demandera à l'utilisateur de
faire le choix d’une combinaison en affichant le message "Entrer une des options affichées" (sans
attendre une réponse !). S’il n’y en a aucune, il affichera le message "Nombre de pièces
insuffisant".
Suggestion : transformez tous les montants en centimes d'euro afin de n’avoir que des entiers dans le
programme
C'est vrai que je le ferais plutôt de manière récursive.
De manière itérative, il faudrait reprendre l'idée de kwariz et son tableau. Une boucle pour incrémenter les pièces de la 1ère case du tableau, dans laquelle on boucle pour incrémenter les pièces de la 2ème case du tableau, etc. en arr^tant les boucles lorsque le total est supérieur ou égal à la somme à atteindre
Ahhhh, je vois ! j'ai compris le concept !
Oui, je sais, ma contribution n'est ni pertinente ni intelligente mais je ne peux pas résiter...
Pour moi, un monnayeur intelligent (mais con pour le banquier) c'est un monnayeur qui me rend plus d'argent que je lui en donne.
...
En tout cas bon courage Bilou51 !
Bonjour,
Bah, au poids, ça existe déjà : des pièces contre un billet !Oui, je sais, ma contribution n'est ni pertinente ni intelligente mais je ne peux pas résiter...
Pour moi, un monnayeur intelligent (mais con pour le banquier) c'est un monnayeur qui me rend plus d'argent que je lui en donne.
...
En tout cas bon courage Bilou51 !
Je suppose, mais l'énoncé reproduit ne le dit pas, qu'il faut gérer les cas où il y a pénurie de certaines pièces, autrement dit le stock des pièces de chaque catégorie n'est pas illimité. Quid ?
Sinon, le problème serait simple : on rend tout en pièces de 1 cent
Dernière modification par danyvio ; 03/05/2013 à 17h05.
On trouve des chercheurs qui cherchent ; on cherche des chercheurs qui trouvent !
Si, l'énoncé le précise:Je suppose, mais l'énoncé reproduit ne le dit pas, qu'il faut gérer les cas où il y a pénurie de certaines pièces, autrement dit le stock des pièces de chaque catégorie n'est pas illimité. Quid ?
Sinon, le problème serait simple : on rend tout en pièces de 1 cent
A+On considérera dans ce programme que les nombres de pièces disponibles de chaque type sont des
constantes définies au départ.
Salut,
le problème de rendu de monnaie (qui consiste notamment à choisir le minimum de pièces à rendre) est un problème dans NP (il n'accepte pas une solution universelle qui permette de trouver une solution dans un temps polynomial).
Vous pouvez écrire un algorithme glouton pour résoudre le problème. Mais il ne trouvera pas toujours la solution optimale dans n'importe quel système de monnaie (lire la page wikipedia pour mieux comprendre).
Vous, vous cherchez à trouver les solutions possibles, ça me parait plus simple.
1- Créez une structure pour accueillir la monnaie disponible.
exemple pour pascal
2- Pour une valeur donnée (exemple objectif == 3,5 euros), tu fais recursivement:Type pieces = (p5cent, p10cents, p50cents, p1euro);
Const piece_val : array[pieces] of Real = (0.05,0.10,0.50,1);
Var dispo: array[pieces] of Integer = (5,10,4,5); {nombre de pièces disponibles}
i - choisir une piece Pi encore disponible dans le moneyeur (n'oubliez pas de décrementer la variable dispo[Pi])
ii -
si objectif - piece_val[Pi] == 0 -> afficher la solution
si objectif - piece_val[Pi] < 0 -> rejeter la piece Pi et choisir une autre piece, aller à i
si objectif - piece_val[Pi] > 0 -> garder la piece Pi et fixer comme nouveau objectif = objectif - piece_val[Pi] (récursion)
c'est un peu vague mais l'idée est là. Il faut aussi penser à enlever les solutions identiques (ex: (1,1,1,0.5) == (1,0.5,1,1)).
Bonne chance.
Exact, mais je m'en étais tenu à la demande initiale...
On trouve des chercheurs qui cherchent ; on cherche des chercheurs qui trouvent !
