【Project Euler】Problem 31: コインの合計

• 本記事はProjectEulerの「100番以下の問題の説明は記載可能」という規定に基づいて回答のヒントが書かれていますので、自分である程度考えてみてから読まれることをお勧めします。

問題 31：コインの合計

原文 Problem 31: Coin sums

問題の要約：1p,2p,5p,10p,20p,50p,£1(100p),£2(200p)のコインを使って£2(200p)にするのは何通りあるか求めよ

再帰呼び出しでの実装です。使うコインの枚数はリストnumcに格納します。リストを引数にすると関数の中で値が変わってしまうのでcopyを使ってコピーを渡すようにしています。特に高速化はしなくても十分早いので行っていません。

このTotal＝10のコードではデバックしやすいように結果のコインリストを表示しています。

from copy import copy
Total = 10                 # Total amount
coins = [200,100, 50, 20,10, 5, 2, 1]     # Coin values
numc = [0 for i in coins]      # store the number of coin used for each coin

def coinsums(cp, numc, r):
  if cp >= len(coins):   # End of coins
    if r == 0:
      print("#",numc)
      return 1
    return 0
  ret = 0
  for i in range(r//coins[cp], -1, -1):  # Descendint order
    numc[cp] = i
    ret += coinsums(cp+1,  copy(numc), r-coins[cp]*i)
  return ret

# input: coin index, list of num of coin, remaining value
print(f"***Answer = {coinsums(0, numc, Total)}")
# [0, 0, 0, 0, 1, 0, 0, 0]
# [0, 0, 0, 0, 0, 2, 0, 0]
# [0, 0, 0, 0, 0, 1, 2, 1]
# [0, 0, 0, 0, 0, 1, 1, 3]
# [0, 0, 0, 0, 0, 1, 0, 5]
# [0, 0, 0, 0, 0, 0, 5, 0]
# [0, 0, 0, 0, 0, 0, 4, 2]
# [0, 0, 0, 0, 0, 0, 3, 4]
# [0, 0, 0, 0, 0, 0, 2, 6]
# [0, 0, 0, 0, 0, 0, 1, 8]
# [0, 0, 0, 0, 0, 0, 0, 10]
***Answer = 11

使うコインのリストを表示する必要がなければ以下の簡単なコードで答えがでます。

coins = [200, 100, 50, 20, 10, 5, 2, 1]     # Coin values
def coinsums1(cp, r):    # coin pointer, remaining value
  if cp >= len(coins):   # End of coins
    if r == 0: return 1
    return 0
  return sum(coinsums1(cp+1, r-coins[cp]*i) for i in range(r//coins[cp], -1, -1))

print(f"***Answer = {coinsums1(0, 200)}")

（開発環境：Google Colab）