Répondre à la discussion
Affichage des résultats 1 à 23 sur 23

Algorithmique




  1. #1
    Gardian7

    Algorithmique

    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

    -----

    Images attachées Images attachées

  2. Publicité
  3. #2
    CM63

    Re : Algorithmique

    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.

  4. #3
    ansset

    Re : Algorithmique

    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.
    Dernière modification par ansset ; 04/12/2018 à 15h48.
    y'a quelque chose qui cloche là dedans, j'y retourne immédiatement !


  5. #4
    PA5CAL

    Re : Algorithmique

    Bonjour

    Citation Envoyé par Gardian7 Voir le message
    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.

  6. #5
    ansset

    Re : Algorithmique

    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 .....
    y'a quelque chose qui cloche là dedans, j'y retourne immédiatement !

  7. A voir en vidéo sur Futura
  8. #6
    PA5CAL

    Re : Algorithmique

    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.

  9. #7
    Jack

    Re : Algorithmique

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

  10. Publicité
  11. #8
    ansset

    Re : Algorithmique

    Citation Envoyé par Jack Voir le message
    ... 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é ?
    y'a quelque chose qui cloche là dedans, j'y retourne immédiatement !

  12. #9
    Jack

    Re : Algorithmique

    Citation Envoyé par ansset Voir le message
    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.

  13. #10
    polo974

    Re : Algorithmique

    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.
    Daudet, tu vas nous manquer...

  14. #11
    Gardian7

    Re : Algorithmique

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

  15. #12
    Jack

    Re : Algorithmique

    Citation Envoyé par Gardian7 Voir le message
    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é)

  16. #13
    Gardian7

    Re : Algorithmique

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

  17. #14
    f6bes

    Re : Algorithmique

    Bjr à tous,
    D'ou l'intérét de payer par carte ou par chéque !!
    Bon je sors vite !
    Bonne journée
    "Ce fut la goutte d'eau de trop qui mit le feu aux poudres!"

  18. #15
    minushabens

    Re : Algorithmique

    Citation Envoyé par Gardian7 Voir le message
    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).

  19. #16
    Gardian7

    Re : Algorithmique

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

  20. #17
    Gardian7

    Re : Algorithmique

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

  21. #18
    PA5CAL

    Re : Algorithmique

    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.

  22. #19
    PA5CAL

    Re : Algorithmique

    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).
    Dernière modification par PA5CAL ; 05/12/2018 à 13h39.

  23. #20
    ansset

    Re : Algorithmique

    Citation Envoyé par minushabens Voir le message
    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.
    y'a quelque chose qui cloche là dedans, j'y retourne immédiatement !

  24. #21
    PHIGE

    Re : Algorithmique

    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

  25. #22
    Gardian7

    Re : Algorithmique

    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

  26. #23
    Ikhar84

    Re : Algorithmique

    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.
    Dernière modification par JPL ; 08/12/2018 à 00h07. Motif: Mise en gras du lien
    J'ai glissé Chef !

Discussions similaires

  1. algorithmique
    Par whisper11 dans le forum Programmation et langages, Algorithmique
    Réponses: 2
    Dernier message: 10/01/2015, 15h30
  2. Algorithmique
    Par mama1234 dans le forum Mathématiques du collège et du lycée
    Réponses: 11
    Dernier message: 17/02/2013, 21h19
  3. Algorithmique
    Par Light11 dans le forum Mathématiques du collège et du lycée
    Réponses: 4
    Dernier message: 25/09/2012, 08h58
  4. Algorithmique
    Par Nidesu dans le forum Mathématiques du collège et du lycée
    Réponses: 3
    Dernier message: 25/02/2012, 23h03
  5. algorithmique
    Par sensor dans le forum Mathématiques du supérieur
    Réponses: 12
    Dernier message: 21/11/2006, 21h28