home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / lang / prolog / 2343 < prev    next >
Encoding:
Text File  |  1993-01-08  |  1.4 KB  |  51 lines
  1. Newsgroups: comp.lang.prolog
  2. Path: sparky!uunet!mcsun!Germany.EU.net!ecrc!acrab60!thom
  3. From: thom@ecrc.de (Thom Fruehwirth)
  4. Subject: Re: British coinage problem
  5. Message-ID: <1993Jan8.131810.18651@ecrc.de>
  6. Sender: news@ecrc.de
  7. Reply-To: thom@ecrc.de
  8. Organization: European Computer-Industry Research Centre GmbH.
  9. References: <8118@skye.ed.ac.uk>
  10. Date: Fri, 8 Jan 1993 13:18:10 GMT
  11. Lines: 38
  12.  
  13. Once you have a simple solution (e.g. my previous posting)
  14. you can make it fast. As we are interested in a set of coins
  15. rather than a sequence of coins as the solution,
  16. we can restrict ourselves to a sorted list (descending by
  17. value). We simply add another argument to sum_coins that
  18. holds the previous value and take care that the new value
  19. is not greater.
  20.  
  21. The resulting program gives a 25-fold speed-up on min_coins(119,L).
  22. The average time to compute one of the first 120 solutions is about
  23. 5 milliseconds (Eclipse on Sun SLC). This speed should suffice.
  24. */
  25.  
  26. % British coinage problem
  27.  
  28. min_coins(Value,Coins):- list(Coins),sum_coins(Coins,Value,Value). 
  29.  
  30. list([]).
  31. list([X|L]):- list(L).
  32.  
  33. sum_coins([],0,_).
  34. sum_coins([Coin|Coins],Sum,PrevVal):-
  35.     coin(Coin,Value),
  36.     Value =< PrevVal,
  37.     Value =< Sum,
  38.     NewSum is Sum-Value,
  39.     sum_coins(Coins,NewSum,Value).
  40.  
  41. coin('ten shilling note', 120).
  42. coin(       'half-crown',  30).
  43. coin(           'florin',  24).
  44. coin(         'shilling',  12).
  45. coin(         'sixpence',   6).
  46. coin(   'threepenny bit',   3).
  47. coin(            'penny',   1).
  48.  
  49. % thom
  50.  
  51.