Coins
Coins
How do you choose the coins in your pocket to pay something? There is an algorithm to use the max numbers of coins? Of course there is, as shown in the book “L’algoritmo del parcheggio” (The parking algorithm) by Prof. Furio Honsell. This GUI help you to choose the exact combination of coins that you have in your pocket to pay the bill.
For example: Suppose you are in Naples (Italy, my city) and have in your pocket this situation. Now you are in “Piazza del Plebiscito” and you want to drink a coffee in the famous “Gambrinus” Bar. You go to the cash, order the coffee and the beautiful cashier give you the sales cash asking 0.80 euro (I wish…). All these coins in your pocket are very heavy to carry, and so you want to give as many as possible coins to the cashier (that will be happiest to have all these coins in the cash to give them as change). The situation can be resumed into a mathematical model:
|
Value (values) |
Quantity (coinsin) |
Total (coinval) |
Cumulative sum (V) |
|
0.01€ |
6 |
0.06€ |
0.06€ |
|
0.02€ |
5 |
0.10€ |
0.16€ |
|
0.05€ |
5 |
0.25€ |
0.41€ |
|
0.10€ |
5 |
0.50€ |
0.91€ |
|
0.20€ |
2 |
0.40€ |
1.31€ |
|
0.50€ |
1 |
0.50€ |
1.81€ |
|
1€ |
1 |
1€ |
2.81€ |
|
2€ |
1 |
2€ |
4.81€ |
|
TOTAL |
26 |
4.81€ |
4.81€ |
The bill to pay is stored into the T variable. As you can see, it is possible to us all coins less than 0.20€ to pay the bill. But what is the most efficient methods?
1 2 3 4 5 6 7 8 | while T>0 %saddle the cashier with coins V0=find(V>T,1,'first'); %find the first value in the V array greater than T coinsout(V0)=coinsout(V0)+1; %give the coin to the cashier coinsin(V0)=coinsin(V0)-1;%this coin is no more in your pocket coinval(V0)=coinval(V0)-values(V0); %update the array V=cumsum(coinval); %update the array T=T-values(V0); %update the bill to pay end |
But is it truly so simple? No, of course. The floating point representation of cents sometimes creates troubles: for example: 1.0000-1 could not be 0 but 1.45782e-17 (that is >0…. ). To fix this problem, multiply (and after divide before printing results) by 100: values, coinval and T.
Finally, this is the result:
If any problems occurs in execution, or if you found a bug, have a suggestion or question just contact me at: giuseppe dot cardillo-edta at poste dot it
You can visit my homepage http://home.tele2.it/cardillo
My profile on XING http://www.xing.com/go/invita/13675097
My profile on LinkedIN http://it.linkedin.com/in/giuseppecardillo
Download Now
Popularity: 1% [?]
Translator
By N2H Follow Us
Video Posts
-
