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