嵇爾的吐槽

#没事画轮子的嵇尔不定期的(W)碎(E)碎(B)念(B)和(L)吐(O)槽(G)

Problem 31 Coin sums 2016-10-12 09:41:00

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 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p

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


硬币求和

英国的货币单位包括英镑£和便士p,在流通中的硬币一共有八种:

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

以下是组成£2的其中一种可行方式:

1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p

不限定使用的硬币数目,组成£2有多少种不同的方式?

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


def process(price, coin_table):
    result = 0
    for coin in coin_table:
        times = price / coin
        if times:
            for t in range(1, times + 1):
                leave = price - t * coin
                if leave > 0:
                    result += process(leave,
                                      coin_table[coin_table.index(coin) + 1:])
                elif leave == 0:
                    result += 1
    return result

print process(200, coins)

感想:

  1. 虽然递归是效率最差的,但是我还是用了递归
  2. 不需要的数据就扔掉
评论共