home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / lang / prolog / 2336 < prev    next >
Encoding:
Internet Message Format  |  1993-01-08  |  1.6 KB
  1. Path: sparky!uunet!spool.mu.edu!agate!doc.ic.ac.uk!uknet!edcastle!aiai!ken
  2. From: ken@aiai.ed.ac.uk (Ken Johnson)
  3. Newsgroups: comp.lang.prolog
  4. Subject: Re: British coinage problem
  5. Message-ID: <8118@skye.ed.ac.uk>
  6. Date: 8 Jan 93 11:19:25 GMT
  7. References: <1993Jan7.141322.22240@ecrc.de>
  8. Sender: news@aiai.ed.ac.uk
  9. Followup-To: comp.lang.prolog
  10. Organization: William's Wonderful Wonky Widget Warehouse
  11. Lines: 43
  12.  
  13.  
  14. In article <1993Jan7.141322.22240@ecrc.de> thom@ecrc.de writes:
  15.  
  16. #  min_coins(Value,Coins):-
  17. #      list(Coins),
  18. #      sum_coins(Coins,Value).
  19. #  
  20. #  list([]).
  21. #  list([X|L]):- list(L).
  22. #  
  23. #  sum_coins([],0).
  24. #  sum_coins([Coin|Coins],Sum):-
  25. #      coin(Coin,Value),
  26. #      Value =< Sum,
  27. #      NewSum is Sum-Value,
  28. #      sum_coins(Coins,NewSum).
  29. # ...
  30. # coins detail omitted
  31.  
  32.  
  33. This is a short solution, but it is really just a neat way of doing
  34. iterative deepening.  To be honest, I hadn't thought of doing it quite
  35. this way.  However, it might be spectacularly inefficient.  Supposing
  36. the fewest coins needed to make up some sum is seven.  This algorithm
  37. will try a large number of combinations of 2 coins, then 3, then 4, then
  38. 5, then 6, before finding the optimal solution.  So this does not really
  39. qualify as the Ultimate Answer. 
  40.  
  41. Adding a clause
  42.  
  43.    sum([],X) :-
  44.     X > 0,
  45.     write('failed'),
  46.     nl.
  47.  
  48. will print the word `failed' for each unsuccessful combination.
  49.  
  50. Ken Johnson
  51. -- 
  52. Son, all the pretty, intelligent, healthy     #    Ken Johnson, AIAI,
  53. young women are taken. It's a basic rule of   #    80 South Bridge, Edinburgh
  54. the universe, and if you don't like it, go    #    Tel 031-650 2756 
  55. somewhere else.        -- my dad  1906-1992   #    Fax 031-650 6513
  56.