Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Algorithme pour rendre la monnaie


Sujet :

Algorithmes et structures de données

  1. #1
    Nouveau Candidat au Club
    Algorithme pour rendre la monnaie
    Problematique:

    Aujourd'hui, les magasins sont de plus en plus équipés de distributeurs automatiques. La plupart de ces machines n'acceptent le paiement que par carte de crédit, malgré le fait qu'une partie importante des consommateurs continuent de payer les marchandises en espèces.
    L'un des problèmes posés par les transactions en espèces est de savoir comment retourner la monnaie: quel est le moyen optimal de restituer un certain montant, avec le nombre minimum de pièces et de billets? C'est un problème que nous rencontrons tous les jours et le problème est le même pour les caisses automatiques.
    Dans cet exercice, vous êtes invité à essayer de trouver une solution optimale pour retourner la monnaie dans un cas très spécifique: lorsque la machine ne contient que des pièces, des billets et des billets. 2 € 5 € 10 €
    Pour simplifier le problème, nous imaginons que toutes ces pièces et billets sont disponibles en quantités illimitées.
    Voici quelques exemples de la façon dont le changement peut être retourné: Changement pour des solutions possibles Solution optimale 1 € ImpossibleImpossible 6 € = (2 € + 2 € + 2 €), 10 € = (2 € + 2 € + 2 € + 2 € + 2 € ), 11 € = (2 € + 2 € + 2 € + 5 €)
    Le changement est représenté comme un objet. Cet objet a trois propriétés:, et lesquelles Change coin2 bill5 bill10 représentent les nombres de 2 €, 5 € et 10 €.
    Par exemple, lorsqu'il est appliqué à l'exemple # 2 du tableau ci-dessus (6 €), nous devrions obtenir un objet avec Modifier les valeurs suivantes: la valeur est 3 (3 pièces de 2 €) la valeur est 0 (pas de billet de 5 €) la valeur est 0 (pas de billet de 10 €) coin2 bill5 bill10 Implémentez la méthode qui retourne un objet. La somme des pièces et des billets OptimalChange (long s) Change indiqués dans l'objet doit être. S'il n'est pas possible de restituer le changement - comme dans l'exemple # 1 Change s -, la méthode doit retourner. nul
    Pour obtenir un nombre maximum de points, votre solution doit toujours fournir un résultat - lorsque cela est possible - avec le nombre minimal de billets et de pièces.
    Remarque: est un qui satisfait la contrainte suivante: 0 <<= 2 63 - 1 (9223372036854775807).

    Solution proposé:
    Code C# :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
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;
     
    namespace GivingChange
    {
        class Program
        {
            static void Main(string[] args)
            {
                Console.Write("Montant?");
                long mnt = Convert.ToInt32(Console.ReadLine());
     
                Console.Write("à Payer?");
                long Payer = Convert.ToInt32(Console.ReadLine());
     
                long Reste = Payer - mnt;
                Console.Write("le reste " + optimalChange(Reste) );
            }
     
        class Change
            {
                public long coin2 = 0;
                public long bill5 = 0;
                public long bill10 = 0;
            }
     
        static Change optimalChange(long s)
            {
                long change = s;
                Change c = new Change();
                if (change == 1)
                    c = null;
     
                if (change >= 10)
                {
     
                        c.bill10 = Sup10EtResteImpaire(change).bill10;
                        if( CalculerReste(change,10)>=2)
                            change = CalculerReste(change, 10);
     
                }
     
                if (  change >= 5 &&  change < 10)
                {
     
                        c.bill5 = Sup5EtResteImpaire(change).bill5;
                        if (CalculerReste(change, 5) >= 2)
                            change = CalculerReste(change, 5);
     
                }
     
                if (change >= 2 && change < 5)
                {
     
     
                        c.coin2 = Sup2EtResteImpaire(change).coin2;
                        if (CalculerReste(change, 2) >= 2)
                            change = CalculerReste(change, 2);
     
                }
     
                return c;
            }
     
           static Change Sup2EtResteImpaire(long s)
            {
                Change c = new Change();
     
                if (s >= 2 && s < 5  )
                {
                    long NumPaireOfS = (s - CalculerReste(s, 2)) / 2;
                    c.coin2 = NumPaireOfS;
                }
     
     
                return c;
            }
     
           static long CalculerReste(long  n, long n2)
            {
                return n % n2;
            }
     
        }
    }

  2. #2
    Rédacteur/Modérateur

    Ta solution est peut-être bonne, peut-être pas.
    Ici, les gens s'intéressent à l'algorithme.
    Décris ton algorithme.
    La traduction de l'algorithme en C#, en Python, en JS ou en n'importe quel langage, c'est de la simple traduction.
    Ici, tu trouveras des gens pour te dire si l'algorithme en français est bien ou pas.
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  3. #3
    Responsable Qt & Livres



    A priori, le code est correct, mais pas génial du tout. Pourquoi autant de classes ? Pourquoi autant de méthodes ? On ajoute une pièce dans l'énoncé et tu es bon pour réécrire une bonne partie.

    (Aussi, tu as implémenté l'algorithme glouton, qui fonctionne pour la majorité des systèmes de pièces tant que toutes les pièces sont disponibles. Ça correspond sûrement à ton besoin scolaire actuel, mais ça pourrait être bien de te renseigner sur l'algorithme dynamique pour gérer le problème en toute généralité.)
    Vous souhaitez participer aux rubriques Qt ou PyQt (tutoriels, FAQ, traductions), HPC ? Contactez-moi par MP.

    Créer des applications graphiques en Python avec PyQt5
    Créer des applications avec Qt 5.

    Pas de question d'ordre technique par MP !

  4. #4
    Expert confirmé
    salut

    tout ceci me rappel mon premier exo d'informatique il y a fort longtemps

    pour rendre la monnaie de façon optimal au moment T
    c'est de décrémenter les éléments maximal entrant dans la composition de ta monnaie

    exemple tu a 33 euros a rendre
    dans ton monnayeur tu as un billet de 1*50€ 2*20€ 4*5€ 6*2€ et 10*1€

    on commence donc par les valeur maxi
    est ce que 50 peut te permettre de rendre la monnaie ... Non on passe au suivant
    est ce que 20 peut te permettre de rendre la monnaie ... Oui donc on prend 20 ce qui dans notre monnayeur nous décrémente le nombre de 20
    et dans la monnaie a rendre on enlève 20
    reste donc 13 a rendre et notre monnayeur n'as plus que 1*50€ 1*20€ 4*5€ 6*2€ et 10*1€ d’élément restant

    on recommence avec 13
    est ce que 50 peut te permettre de rendre la monnaie ... Non on passe au suivant
    est ce que 20 peut te permettre de rendre la monnaie ... Non on passe au suivant
    est ce que 5 peut te permettre de rendre la monnaie ... Oui .... a toi de faire la suite

    on peut optimiser pour ne recommencer la boucle qu'a l’endroit ou l'on s'est arrêté dans le monnayeur
    Nous souhaitons la vérité et nous trouvons qu'incertitude. [...]
    Nous sommes incapables de ne pas souhaiter la vérité et le bonheur, et sommes incapables ni de certitude ni de bonheur.
    Blaise Pascal
    PS : n'oubliez pas le tag

  5. #5
    Rédacteur/Modérateur

    Anapurna,
    Dans l'exercice proposé (on a des pièces de 10, 5 et 2, mais pas de pièce de 1), ta proposition ne convient pas.

    Si le montant à rendre est de 8, tu vas prendre une pièce de 5, et tu vas arriver à une impasse.

    Ici, l'algorithme est :
    Le montant à rendre est il pair ou impair ?

    Si le montant est impair :
    Si montant impair, le montant est il inférieur à 5 ou supérieur ou égal à 5
    Si impair et inférieur à 5 --> pas de solution.
    Si impair et supérieur ou égal à 5, on donne une pièce de 5, et on se ramène au cas où le montant est pair ( nouveau montant = montant-5)

    Si le montant est pair :
    tant que montant > 10, donner une pièce de 10 et décrémenter le montant de 10
    Tant que montant > 2 , donner une pièce de 2, et décrémenter le montant de 2.
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  6. #6
    Expert confirmé
    salut

    dans c'est cas la si je ne trouve pas la solution
    je descend de 1 la première catégorie et je recommence
    jusqu’à trouver la solution
    ce n'est pas un problème c'est un peut le même principe que de parcourir un arbre
    si la racine ne convient pas tu déplace la racine
    le but étant d’être le plus exhaustif possible et de t’arrêter a la première solution
    Nous souhaitons la vérité et nous trouvons qu'incertitude. [...]
    Nous sommes incapables de ne pas souhaiter la vérité et le bonheur, et sommes incapables ni de certitude ni de bonheur.
    Blaise Pascal
    PS : n'oubliez pas le tag

  7. #7
    Responsable Qt & Livres

    Citation Envoyé par anapurna Voir le message
    pour rendre la monnaie de façon optimal au moment T
    c'est de décrémenter les éléments maximal entrant dans la composition de ta monnaie
    Non, cette manière de faire n'est pas toujours optimale, ça dépend des pièces disponibles : dans le pire cas, le meilleur algorithme sera toujours exponentiel (sauf si P=NP). La seule manière véritablement optimale (et classique) est d'utiliser l'algorithme de programmation dynamique : https://fr.wikipedia.org/wiki/Probl%...tion_dynamique
    Vous souhaitez participer aux rubriques Qt ou PyQt (tutoriels, FAQ, traductions), HPC ? Contactez-moi par MP.

    Créer des applications graphiques en Python avec PyQt5
    Créer des applications avec Qt 5.

    Pas de question d'ordre technique par MP !

  8. #8
    Nouveau Candidat au Club
    Citation Envoyé par tbc92 Voir le message
    Ta solution est peut-être bonne, peut-être pas.
    Ici, les gens s'intéressent à l'algorithme.
    Merci pour ton commentaire, J'ai décris cette solution par ce que je n'ai trouvé la solution de ce Algorithme dans différents Forum fracophone,c'est ça mon but,en effet, j'ai codé une solution je l'a testé, elle fonctionne bien

    Citation Envoyé par anapurna Voir le message
    salut

    tout ceci me rappel mon premier exo d'informatique il y a fort longtemps
    merci bcp pour ta proposition

    Citation Envoyé par anapurna Voir le message
    dans c'est cas la si je ne trouve pas la solution
    je descend de 1 la première catégorie et je recommence
    jusqu’à trouver la solution
    ce n'est pas un problème c'est un peut le même principe que de parcourir un arbre
    si la racine ne convient pas tu déplace la racine
    le but étant d’être le plus exhaustif possible et de t’arrêter a la première solution
    J'ai essayé de couvrir tous les cas possible, vous pouvez tester et vous allez voir

    Citation Envoyé par dourouc05 Voir le message
    A priori, le code est correct, mais pas génial du tout. Pourquoi autant de classes ? Pourquoi autant de méthodes ? On ajoute une pièce dans l'énoncé et tu es bon pour réécrire une bonne partie.
    dans le bonne pratique , il vaut mieux décortiquer le code sous des méthodes et des fonctions.