Project Euler 031
イギリスでは硬貨はポンド£とペンスpがあり，一般的に流通している硬貨は以下の8種類である.
1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).
以下の方法で£2を作ることが可能である．
1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p
これらの硬貨を使って£2を作る方法は何通りあるか?
->次の問題
考え方
プログラミングらしくて楽しい問題ですね。問が再帰関数を使えと言っています。
設問の£2=200pをmoneyとして
大きい硬貨から順に、0~(money/コインの価値)枚のパターンで分け使った分をmoneyから引きます。残ったお金を残りの硬貨で作れるパターンを再帰関数で取得します。
今回は1pがあるので、再帰関数の最後は必ず1を返しますが、例えば[3,7,11]でmoney=100になる組み合わせのように、再帰関数の最後で組み合わせが成立しない場合も考慮し1または0を返すようにしています。
実はリストは昇順じゃなくても同じ結果を返しますが、無駄な計算が増えるので遅くなります。
euler031.py
def combo_of_coin(money: int, coin_list: list):
"""コインの組み合わせ数を返す再帰関数
Args:
money: 金額
coin_list: 組み合わせに使用するコインの価値、昇順で記載。
Returns:
int: コインの組み合わせ数
"""
result = 0
# リストの最後に来たら
if len(coin_list) == 1:
# 基本的には1を返す。
# moneyを割り切れない場合=組み合わせが成立しない場合0を返す
return 1 if money % coin_list[0] == 0 else 0
# 検証に使用するコインを末尾から取り出す
coin = coin_list[-1]
# coinを使う枚数は0~(money//coin)の(money//coin +1)通り
for i in range(money // coin + 1):
# coinの分をmoneyから差し引き、
# 残りのcoin_listから再帰的に組み合わせを取得しresultに加算
result += combo_of_coin(money - coin * i, coin_list[:-1])
return result
コード
euler031.py
def main():
money = 200
coin_list = [1, 2, 5, 10, 20, 50, 100, 200]
print(combo_of_coin(money, coin_list))
def combo_of_coin(money: int, coin_list: list):
"""コインの組み合わせ数を返す再帰関数
Args:
money: 金額
coin_list: 組み合わせに使用するコインの価値、昇順で記載。
Returns:
int: コインの組み合わせ数
"""
result = 0
# リストの最後に来たら
if len(coin_list) == 1:
# 基本的には1を返す。
# moneyを割り切れない場合=組み合わせが成立しない場合0を返す
return 1 if money % coin_list[0] == 0 else 0
# 検証に使用するコインを末尾から取り出す
coin = coin_list[-1]
# coinを使う枚数は0~(money//coin)の(money//coin +1)通り
for i in range(money // coin + 1):
# coinの分をmoneyから差し引き、
# 残りのcoin_listから再帰的に組み合わせを取得しresultに加算
result += combo_of_coin(money - coin * i, coin_list[:-1])
return result
if __name__ == '__main__':
from time import time as t
st = t()
main()
print(t() - st, 'sec')
paizaにて実行
結果 73682 0.019005775451660156 sec