home *** CD-ROM | disk | FTP | other *** search
- Path: sparky!uunet!pipex!bnr.co.uk!uknet!edcastle!aiai!ken
- From: ken@aiai.ed.ac.uk (Ken Johnson)
- Newsgroups: comp.lang.prolog
- Subject: Making up sums of money from coins
- Message-ID: <8088@skye.ed.ac.uk>
- Date: 5 Jan 93 15:14:10 GMT
- Sender: news@aiai.ed.ac.uk
- Followup-To: comp.lang.prolog
- Organization: William's Wonderful Wonky Widget Warehouse
- Lines: 72
-
-
- If you want to make up a sum of money in British decimal currency using
- the fewest coins, there is a safe deterministic algorithm. Allocate the
- largest coin that you can, until you have made up the sum exactly. E.g.
- to make up 78p you allocate 50p (the largest coin -- no one-pound coins
- in Scotland), leaving 28p; to make up 28p you allocate 20p (the largest
- coin that fits) leaving 8p, then 5p, 2p, 1p. A few experiments
- convinces me this algorithm works.
-
- In old British money, however, it sometimes misses a trick. The
- following code works for the cases of two shillings and twopence (26
- pence) and two shillings and sixpence (30 pence) as follows:
-
- | ?- make(26,C).
-
- C=[florin,penny,penny] ;
-
- | ?- make(30,X).
-
- X=[half-crown] ;
-
- But it can't do four shillings (48 pence) correctly.
-
- | ?- make(48,X).
-
- X=[half-crown,shilling,sixpence]
-
- since a solution in two coins is possible. I'd be interested to hear of
- any neat, deterministic algorithm that can do this problem even though
- it is now twenty-one years too late. I'm looking for something neater
- than a depth first search with depth-of-search control.
-
- Here is my code, for the information of any who seek it. You may
- distribute this code freely, but please acknowledge the source and the
- limitation described above. If you sell copies of this code at a
- profit, I want a share.
-
-
- % Making up sums of pence in old British
- % currency. Ken Johnson, 5-1-1993
-
- make(0,[]).
-
- make(Sum,[Name|Rest]) :-
- coin(Name,Value),
- Value =< Sum,
- !,
- Residue is Sum - Value,
- make(Residue,Rest).
-
-
- % Note the ordering from greatest to least
- % value is essential to make the second clause
- % (above) work. If these clauses are randomly
- % ordered you will have to alter that second clause
- % to make it cope.
-
- coin('ten shilling note',120).
- coin('half-crown',30).
- coin(florin,24).
- coin(shilling,12).
- coin(sixpence,6).
- coin('threepenny bit',3).
- coin(penny,1).
-
-
-
- --
- Son, all the pretty, intelligent, || Ken Johnson healthy young women are taken. || A I Applications Institute
- It's a basic rule of the universe, || 80 South Bridge and if you don't like it, || Edinburgh, Scotland EH1 1HN
- go somewhere else. || Phone 031-650 2756 Fax 031-650 6513
- -- my dad 1906-1992 || E-mail ken@aiai.ed.ac.uk
-