coins = [2,1,0.5,0.2,0.05, 0.02, 0.01]
# want: a function that, given a list of coin values and a goal,
# returns the number of ways of reaching the goal given those coins.
# It should be call itself recursively. The base case will be when the
# list of coin values contains only a single value.
def recurse_coins(target, coins):
## return number of combinations of coins that add to targets.
## could do this with itertools. But more fun to work out a recursive
## solution. first, use biggest coin. work out how many ways to
## make up remainder. Base case:
## 2
## + 1 [1,...]
## +
ways = 0
if len(coins) == 1:
return 1
else:
for coin in coins:
coins.remove(coin)
sub = 0
while sub<target:
ways += 1
sub += coin
remainder = target - sub
if remainder > 0:
new = recurse_coins(remainder, coins)
ways += new
return ways
def counter (target, coins):
# return the number of ways of making up target with coins (it's guaranteed
# that there will always be a way with UK coins). In a recursive solution, we start with coin 1, see how many
# times it divides target. target/coin = n, there will be a base way for each i in range(0,n+1)
# if there are 2 ways using coin 1, and the second way
ways = 0
if len(coins) == 1:
return 1
first_coin = coins[0]
remaining_coins = coins[1:]
first_coin_combs = int(target/first_coin)
for i in range(0,first_coin_combs+1):
first_coin_total = i*first_coin
remainder = target - first_coin_total
ways += counter(remainder, remaining_coins)
return ways
coins = [2,1,0.5,0.2,0.05, 0.02, 0.01]
print counter (2, coins)
target = 200
coins = [1, 2, 5, 10, 20, 50, 100, 200]
ways = [1] + [0]*target
print ways
for coin in coins:
for i in range(coin, target+1):
ways[i] += ways[i-coin]
print "Ways to make change =", ways[target]