```(Writing a program that returns the number of ways to make change for a
certain ammount.)

> Well it's not much but here is my attempt. I gave up on it since it didn't
> seem like anyone was interested in pursuing it any further. It can calculate
> the number of possiblities for \$100 in 1 hour 23 min.
> ...

Here is my variant. It does \$100 in 2.5s, \$1000 in 31.2 s and
\$10000 in 343s without any precomputation. (Time is approximately linear
in the ammount.)

It is built on a recursive algorithm which can be found at
http://www.telospub.com/journal/MIER/Piele/Vol6No1/Piele613.html

To run fast it uses a buffer to store the computed values and uses an
iterative rather than recursive algorithm. To reduce the memory requirements
and the garbage collection/thrashing, the buffer does not store all values,
but only the last 10001 ones (fewer if we ask for change for a smaller
ammount than \$100).

COINS = [1,5,10,25,50,100,200,500,1000,2000,5000,10000]

def ways(sum)
used_coins = COINS.find_all {|c| c<=sum}
buffer_size = used_coins.max + 1

buffer = [Array.new(buffer_size,1)]
(used_coins.size-1).times {buffer << Array.new(buffer_size,0)}

0.upto(sum) do |value|
1.upto(used_coins.length-1) do |used|
i = value % buffer_size
buffer[used][i] = buffer[used-1][i] +
buffer[used][(value-used_coins[used])%buffer_size]
end
end
return buffer[used_coins.size-1][sum % buffer_size]
end

ARGV.each {|x| puts ways(x.to_i)}

// Niklas

```