| Author |
 Replies: 8 / Views: 1,857 |
|
|
New Member
United Kingdom
4 Posts |
I've been looking for currencies which don't follow the 1-2-5 series (i.e. te UK, Europe etc) or the 1, 2.5, 5 type series (i.e. USA).
In particular I'm interested to know if there are currencies still used in which a greedy algorithm to make up change (i.e. sequentially adding the biggest possible coin which is less than the remaining total) does not work.
Pre-decimalisation UK currency is one example in which to make up 48 pence, for example, the greedy algorithm would first select the half-crown followed by the shilling and the six-pence. Two florins, however, would make 48 pence in two coins instead of three.
Typically these will be sequences of coins which don't at least double between denominations.
If you know of any examples, your help would be much appreciated.
|
|
|
|
Pillar of the Community
Sweden
1078 Posts |
The ones I can think of immediately are denominations of three: Azerbaijan, 3 Qepik  Kyrgyzstan, 3 Som  Transnistria, 3 Rubles (plastic coin!)  Cuba, 3 Pesos (note; non-covertible Cuban Pesos) And then of course there are many, many currencies that only have the 1-5-10-50 and so on series, although not entirely the same as the two series you mention it's about the same, just missing a denomination inbetween which makes denominations of 1 very common. |
|
New Member
 United Kingdom
4 Posts |
Thanks for your quick response. This is almost exatly what I was looking for.
Unfortunately although these are great examples of systems where the coins don't at least double between denominations, the greey algorithm still works for 1,3,5 sets.
For example to make 6, the greedy algorithm chooses 5 and then 1. Although you can also do this with two 3s you can't do it with fewer than two coins.
1,3,4 fails the test though, because to make 6 the greedy algorithm would use 4 followed by two 1s, but clearly again this could be done with just two 3s.
Thanks so much for the response though.
Any more unusual ones like these would be more than welcome. I am happy to check them all out.
|
|
Pillar of the Community
Russian Federation
5172 Posts |
...Wouldn't the greedy algorithm fail on the 1-2.5-5 series? Starting with a value of 3 or 4, it will chooce the 2.5 coin and get stuck (unless there was a 0.5, which there admittedly usually was). Ditto 2-5-10 without a 1 for a value of 6 or 8 (this was surprisingly common historically). Can't think of a modern example of either though (Netherlands Antilles looks like they would count, but their 2 1/2 cent coins were demonetized a while back; ditto Venezuela and their weird 12 1/2 cent coins). I guess that anything that has both a 20 and a 25 (without a 15 and/or a value in the 26-40 range) would fail on 40, which would technically include modern USA and UK, and non-technically include pre-euro Belgium. Can't think of any useful modern examples. (...Oh, right, Tajikistan.) OTOH, as far as I can see, neither the 1-3-5 system nor the 1-2-3-5 system actually fails anywhere with the greedy method. (If so, this eliminates Kyrgyzstan, as well as Bahamas, the only place to still have a 15 cent coin, because their denominations go 5-10-15-25, which is equivalent to 1-2-3-5.) |
|
Moderator
 United States
188110 Posts |
 to the Community! Your post was moved to the appropriate forum for the proper attention.  |
|
Bedrock of the Community
Canada
24885 Posts |
To the Forum. |
|
New Member
United Kingdom
4 Posts |
Thanks for the welcomes and thanks @january1may for the great answer.
I agree with you that 1-2.5-5 will fail if it is for the lowest decade/denomination. Perhaps there are currencies for which this is the case. I am not sure. For the US example I was thinking of, the 1-2.5-5 series is actually 10c-25c-50c, so to make 40, the greedy algorithm still works because there are smaller coins. If the 1-2.5-5 series is in the smallest denomintion though I completely agree with you that the greedy algorithm gets stuck. Are there any such exampes? I suppose I should restrict my self to systems wehre all possible integer values of change can be made.
You said "Can't think of any useful modern examples. (...Oh, right, Tajikistan.)"
Tajikistan sounds like a legitimate answer to me with 5, 10 ,20, 25, 50 somoni. Are all these coins still in circulation or have the 25 somoni coins been phased out?
Thanks
|
|
Pillar of the Community
Russian Federation
5172 Posts |
Quote:
Are all these coins still in circulation or have the 25 somoni coins been phased out? The 25 diram (not somoni) coins have been discontinued, i.e. not included in the 2011 redesign. To the best of my knowledge, all of them should still be in circulation; they're certainly all legal tender. (I've never actually been to Tajikistan, so I cannot comment more precisely; I have heard what they do to Russian coin collectors, so it's unlikely that I'd ever end up there either.) |
|
New Member
United Kingdom
4 Posts |
Ah, fantastic, thankyou. That makes a lot of sense. If hey're still in circulation then that works for me.
|
| |
Replies: 8 / Views: 1,857 |
|
Posted 09/29/2018 7:53 pm
