Discussion :

[mr diablomano]

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;
        }
 
    }
}

[tbc92]

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.

[dourouc05]

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é.)

[anapurna]

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

[tbc92]

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.

[anapurna]

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

[dourouc05]

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

[mr diablomano]

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

salut

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

merci bcp pour ta proposition

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

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.