James Gray
1/27/2008 11:08:00 PM
[Note: parts of this message were removed to make it a legal post.]
Begin forwarded message:
> From: "Clark Grubb" <clarkgrubb@gmail.com>
> Date: January 27, 2008 1:04:14 PM CST
> To: submission@rubyquiz.com
> Subject: Please Forward: Ruby Quiz Submission
>
> This is a recursive solution. We prune the possibilities needing
> examination by observing that if a coin has value N, then among N
> coins of
> lesser value, it will be possible to replace some of them with fewer
> coins of value N. If we could not do this, each combination of the
> lesser coins
> would have to have a different value modulo N, none of which could
> be 0 modulo N.
> --------------------------
>
> def make_change_aux(amount, coins)
> coin = coins.first
> if 1 == coins.size
> return 0 == amount % coin ? [coin] * (amount / coin) : nil
> end
> change = nil
> (amount/coin).downto([ amount/coin - coins[1], 0 ].max) do |n|
> a = make_change_aux(amount - n * coin,
> coins.slice(1, coins.size-1))
> if a and (change.nil? or a.size + n < change.size )
> change = ([ coin ] * n).concat(a)
> end
> end
> change
> end
>
> def make_change(amount, a = [25,10,5,1] )
> coins = a.uniq.sort.reverse
> coins.each do |c|
> raise "Not a positive integer value: #{c}" if c < 1 or c != c.to_i
> end
> if coins.empty?
> return 0 == amount ? [] : nil
> end
> make_change_aux(amount, coins)
> end
>