Problem 31

Problem 31

22 November 2002

In England the currency is made up of pound, £, and pence, p, and there are eight coins in general circulation:

1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).

It is possible to make £2 in the following way:

1£1 + 150p + 220p + 15p + 12p + 31p

How many different ways can £2 be made using any number of coins?

直接用循环

def fun31For(money):
    count = 0
    for a in range(money, -1, -200):
        for b in range(a, -1, -100):
            for c in range(b, -1, -50):
                for d in range(c, -1, -20):
                    for e in range(d, -1, -10):
                        for f in range(e, -1, -5):
                            for g in range(f, -1, -2):
                                count += 1
    return count

效率较高，程序难看了点
answer is 73682, time:0.0160000324249

如果用递归，程序结构清楚点，效率低点，time:0.21799993515, 慢了13倍
    

coins = [200, 100, 50, 20, 10, 5, 2, 1]

def fun31(money, index):
    sum = 0
    if index == 7:
        return 1
    for i in range(index, 8):
        if money - coins[i] == 0:
            sum += 1
        if money - coins[i] > 0:
            sum += fun31(money-coins[i], i)
    return sum
fun31(200， 0)