home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / lang / prolog / 2318 < prev    next >
Encoding:
Internet Message Format  |  1993-01-05  |  2.9 KB

  1. Path: sparky!uunet!pipex!bnr.co.uk!uknet!edcastle!aiai!ken
  2. From: ken@aiai.ed.ac.uk (Ken Johnson)
  3. Newsgroups: comp.lang.prolog
  4. Subject: Making up sums of money from coins
  5. Message-ID: <8088@skye.ed.ac.uk>
  6. Date: 5 Jan 93 15:14:10 GMT
  7. Sender: news@aiai.ed.ac.uk
  8. Followup-To: comp.lang.prolog
  9. Organization: William's Wonderful Wonky Widget Warehouse
  10. Lines: 72
  11.  
  12.  
  13. If you want to make up a sum of money in British decimal currency using
  14. the fewest coins, there is a safe deterministic algorithm.  Allocate the
  15. largest coin that you can, until you have made up the sum exactly.  E.g. 
  16. to make up 78p you allocate 50p (the largest coin -- no one-pound coins
  17. in Scotland), leaving 28p; to make up 28p you allocate 20p (the largest
  18. coin that fits) leaving 8p, then 5p, 2p, 1p.  A few experiments
  19. convinces me this algorithm works. 
  20.  
  21. In old British money, however, it sometimes misses a trick.  The
  22. following code works for the cases of two shillings and twopence (26
  23. pence) and two shillings and sixpence (30 pence) as follows:
  24.  
  25.           | ?- make(26,C).
  26.  
  27.                C=[florin,penny,penny] ;
  28.  
  29.           | ?- make(30,X).
  30.  
  31.                X=[half-crown] ;
  32.  
  33. But it can't do four shillings (48 pence) correctly.
  34.  
  35.           | ?- make(48,X).
  36.  
  37.                X=[half-crown,shilling,sixpence]
  38.  
  39. since a solution in two coins is possible.  I'd be interested to hear of
  40. any neat, deterministic algorithm that can do this problem even though
  41. it is now twenty-one years too late.  I'm looking for something neater
  42. than a depth first search with depth-of-search control. 
  43.  
  44. Here is my code, for the information of any who seek it.  You may
  45. distribute this code freely, but please acknowledge the source and the
  46. limitation described above.  If you sell copies of this code at a
  47. profit, I want a share. 
  48.  
  49.  
  50.           % Making up sums of pence in old British
  51.           % currency.  Ken Johnson, 5-1-1993
  52.  
  53.           make(0,[]).
  54.  
  55.           make(Sum,[Name|Rest]) :-
  56.               coin(Name,Value),
  57.               Value =< Sum,
  58.               !,
  59.               Residue is Sum - Value,
  60.               make(Residue,Rest).
  61.  
  62.  
  63.           % Note the ordering from greatest to least
  64.           % value is essential to make the second clause
  65.           % (above) work. If these clauses are randomly
  66.           % ordered you will have to alter that second clause
  67.           % to make it cope.
  68.  
  69.           coin('ten shilling note',120).
  70.           coin('half-crown',30).
  71.           coin(florin,24).
  72.           coin(shilling,12).
  73.           coin(sixpence,6).
  74.           coin('threepenny bit',3).
  75.           coin(penny,1).
  76.  
  77.  
  78.  
  79. -- 
  80. Son, all the pretty, intelligent,      || Ken Johnson                           healthy young women are taken.         || A I Applications Institute
  81. It's a basic rule of the universe,     || 80 South Bridge                       and if you don't like it,              || Edinburgh,  Scotland   EH1 1HN
  82. go somewhere else.                     || Phone 031-650 2756   Fax 031-650 6513
  83.                -- my dad  1906-1992    || E-mail ken@aiai.ed.ac.uk
  84.