Algorithmique

[Gardian7]

Bonjour les amis
Aidez-moi à résoudre cet algorithme svp:

" Calculer un rendu de monnaie en fonction de la valeur des pièces et des billets, en déterminant combien de billets de telle valeur ou de pièces de telle valeur il faut rendre. Transformer une somme en coupure correspondantes. 1898,7 € qui se décompose en :
3 billets de 500€
1 billet de 200€
1 billet de 100€
1 billet de 50€
2 billets de 20€
1 billet de 5€
1 pièce de 2€
1 pièce de 1€
1 pièce de 50 centimes
1 pièce de 10 centimes
1 pièce de 5 centimes
1 pièce de 2 centimes


Et c'est avec ça qu'on me demande d'écrire un algorithme qui le résoudre.

Je suis sérieusement bloqué et je crie à l'aide
-----

[CM63]

Bonjour,

A quel moment es-tu bloqué? Si tu es bloqué dès le départ, cela voudrait dire que ton prof te demande de faire un exercice pour lequel on ne t'as pas formé, chose à laquelle on ne crois pas. Et si c'est le cas, nous ne pouvons rien pour toi, il faut t'adresser à ton prof.

[ansset]

j'ajoute que l'énoncé est ambiguë car il n'y a pas une réponse unique possible.
avec un bon paquet de pièces , on pourrait rendre la somme avec uniquement des pièces de 5 centimes plus 1 pièce de 2 centimes.
je pense néanmoins que cet exercice peut faire appel aux restes par divisions succéssives.
en optimisant le nb d'éléments rendus par exemple.
exemple :
combien de billets max de 500 euros ?
que reste t il ?
combien de billets max de la valeur inférieure pour le reste à rembouser ?
etc.

[PA5CAL]

Bonjour

Je suis sérieusement bloqué et je crie à l'aide

Soyons sérieux.

Cet algorithme est une version très simplifiée (sans limite de disponibilité des billets et des pièces) de celui qu'on déroule naturellement chaque fois qu'on paye en liquide en faisant l'appoint.

Il me semble fort improbable que tu n'aies jamais eu à le faire, et même si c'était le cas, tu pourrais assez facilement trouver le moyen d'y parvenir. Il suffit ici juste d'énoncer la démarche suivie, en bon français.

[A voir en vidéo sur Futura]

[ansset]

indice, il semble clair que le max de billets de 500 est 3 , car 3*500 < somme < 4*500
et 3 =E(1898,7/500), le reste étant
1898,7-3*500 .....

[PA5CAL]

On pourrait même y arriver sans faire d'autres calculs que des additions, en ajoutant un a un les gros billets, les petits billets, les grosses pièces, etc. . Cette façon de voir permet de clarifier le principe, qui peut ensuite être optimisé comme l'indique ansset.

[Jack]

... ou une suite de soustractions, en commençant par les plus grosses coupures également.

[ansset]

... ou une suite de soustractions, en commençant par les plus grosses coupures également.

Il me semble que c'était exactement la démarche que j'avais proposée.
me suis je mal exprimé ?

[Jack]

Il me semble que c'était exactement la démarche que j'avais proposée.
me suis je mal exprimé ?

Il me semble que les 2 solutions précédentes (et qui fonctionnent également bien sûr) étaient une division entière (ta solution) et une somme (celle de PA5CAL).

Je proposais donc la possibilité de soustractions successives.

Comme quoi un algorithme a bien souvent de nombreuses solutions. Gardian7 a donc l'embarras du choix désormais.

[polo974]

Pour rigoler,
je bosse avec des appareils qui font de l'acceptation et du rendu d'espèce.
un jour un client à introduit un billet de 500.- pour un achat de 3.25 (bref, si c'est pas du blanchiment d'argent...)
l'appareil aurait pu rendre la monnaie, mais ça aurait vider presque tout l'appareil, et le gars aurait dû partir avec quelques kilos de petites pièces...
en fait l'appareil (dont je ne maîtrisait pas l'algo) à fait un serrage...

depuis, à la demande des magasins, on a configuré les appareils pour ne plus accepter de coupure de 500.- et 200.-

(la loi n'oblige pas de faire le rendu, c'est à l'acheteur de faire l'appoint. il n'y a aucune contrainte sur le rendu contrairement au paiement, où le vendeur peut refuser une brouette de pièces de 1cts)

bref, pour revenir au sujet,
passer en centimes pour ne pas utiliser les flottants (sources de mauvaises surprises car il y a des arrondis pas toujours maîtrisés...).
utiliser la division entière dans une boucle itérant sur les valeurs de coupures et pièces triées par ordre décroissant.

en python, un truc pareil doit prendre moins de 10 lignes

pour le fun: (toute) petite complication de l'exo: gérer un stock de coupures et pièces disponibles.

[Gardian7]

Voyez un peu le pdf
C'est comme çà que j'ai essayé de travailler
Vous en dites quoi ?

[Jack]

Vous en dites quoi ?

Que donner ton code sous forme de pdf est une mauvaise idée.
Tu pourrais plus simplement publier ton code sous forme de texte entre balises code (ou bouton # dans l'éditeur avancé)

[Gardian7]

désolé au fait jusque là je ne connais pas encore utilisé les langages de programmation. Alors on m'a d'abord introduit à l'algorithmique, qui est selon mon prof comme un langage universel des programmeurs. Avant bien-sûr de parler de différentes langages de programmation. Donc jusque là je ne suis qu'au d'apprentissage des instructions, les structures itératives,...

[f6bes]

Bjr à tous,
D'ou l'intérét de payer par carte ou par chéque !!
Bon je sors vite !
Bonne journée

[minushabens]

Voyez un peu le pdf
C'est comme çà que j'ai essayé de travailler
Vous en dites quoi ?

ton algorithme m'a l'air correct mais tu peux l'accélérer en calculant en une fois le nombre de coupures d'un certain montant à rendre. Il suffit de faire la division entière. C'est surtout intéressant pour les billets de 500 euros parce que si le montant est de quelques milliards il va en faire des soustractions cet algorithme! (cela dit ça prendra quelques millièmes de seconde au plus).

[Gardian7]

Merci Minushabens, est-ce tu peux montrer par les instructions comme l'accélérer. Comme tu as dit?

[Gardian7]

Comment l'accélérer voulais-je dire.

[PA5CAL]

Il ne s'agit pas vraiment de l'accélérer (en toute rigueur, il n'ira pas plus vite) mais de le rendre plus concis, en remplaçant la séquence des opérations pour différents billets ou pièces par la répétition d'une seule opération avec des paramètres qui vont évoluer.

[PA5CAL]

Un algorithme peut être énoncé en bon français ou dans un pseudo-langage plus proche des opérations réalisables par la machine, et de façon plus ou moins précis quant aux moyens qui seront mis en œuvre pour son codage.

L'algorithme pourrait par exemple s'énoncer sous la forme : « Étant donné un montant, pour chacune des valeurs de billet ou de pièce classées par ordre décroissant de 500€ à 0,01€, dire le nombre maximum de billets ou de pièces dont la somme des valeurs ne dépasse pas le montant puis soustraire cette somme du montant. »

Ce point de vue permet tout aussi bien de produire directement le nombre de billets ou de pièces de chaque valeur, par exemple en le calculant avec la formule indiquée par ansset au post #5, ou bien d'obtenir ce nombre à l'aide d'une répétition de tests et de soustractions ou de sommes.

Mais l'énoncé de l'algorithme pourrait être plus précis, en indiquant explicitement par quel moyen obtenir ce nombre.

Toutefois, plus l'énoncé donne de précision sur la façon de procéder, moins il laisse de liberté quant au choix de la structure du programme et aux opérations utilisées pour son codage.

Or, imposer que le nombre de billets ou de pièces soit calculé à l'aide d'une division entière n'est pas forcément la façon de faire la plus optimale sur un matériel ne disposant pas de la division câblée (ce qui est le cas sur la plupart des petits micro-contrôleurs 8 bits), et inversement, imposer la répétition d'une suite d'opérations n'est pas intéressant si le matériel dispose des opérateurs permettant de calculer directement le résultat. De même, si la répétition d'une même opération paramétrée est plus compacte et occupe moins de mémoire programme qu'une suite linéaire d'opérations, elle prend souvent plus de temps à s'exécuter.

L'écriture d'un algorithme n'est donc pas totalement indépendante de l'implémentation particulière qu'on souhaite en faire (langage et matériel utilisés), ni des objectifs visés (compacité, vitesse ou portabilité du code, par exemple).

[ansset]

ton algorithme m'a l'air correct mais tu peux l'accélérer en calculant en une fois le nombre de coupures d'un certain montant à rendre. Il suffit de faire la division entière. C'est surtout intéressant pour les billets de 500 euros parce que si le montant est de quelques milliards il va en faire des soustractions cet algorithme! (cela dit ça prendra quelques millièmes de seconde au plus).

oui, c'est ce que j'ai essayé d'indiquer en prenant au fur et à mesure les parties Entières de la division de la somme restante par la coupure inférieure.
pour le reste, je crois qu'on demande un algo , pas un programme.

[PHIGE]

Bonjour,

En terme d'efficacité (même si cela n'a pas beaucoup d'importance ici) la seule division à conserver est celle par 500 si la somme est supérieure. Ensuite les restes sont au mieux 2 fois supérieurs au billet/pièce suivant (immédiatement inférieur en valeur faciale) et deux soustractions seront toujours plus rapides qu'une division (même qu'un DivMod pour récupérer directement le reste).

Bon, c'est juste pour le plaisir .

Salutations

[Gardian7]

Merci beaucoup à vous.
Je tiendrai compte de tout ce que vous avez dit.

Si quelqu'un aurait des cours et exercices d'algorithmique. Ça m'aidera beaucoup dans mon apprentissage.

Merci

[Ikhar84]

Voilà un petit cours que je trouve sympa. Regardez en particulier la fonction MOD (modulo), bien sûr comme dit par plusieurs intervenants, un algo n'est que l'expression plus ou moins en bon français du "déroulé" de la logique d'un bout de programme.