問題

最近は電車もバスも電子マネーが当たり前。
でも、いまだに現金払いで払う人も意外に多いもの。
今回はバスに設置されている両替機を考えます。

この機械では、10円玉、50円玉、100円玉、500円玉の組み合わせに両替することができ、
いずれの硬貨も十分な枚数がセットされています。
（バスの運賃は現金の場合は10円単位になっているため、
1円玉、5円玉は取り扱っていません）

両替する際に、使われない硬貨はあっても構いませんが、
バスの中でたくさんの小銭が出ると困るため、
最大で15枚になるように両替します。
例えば1000円を両替するときに、「10円玉を100枚」という両替はできません。

1000円札を入れたときに出てくる硬貨の組み合わせは何通りあるかを求めてください。
なお、硬貨の順番は区別しないものとします。

両替のイメージ.

1000
├ 100, 100, 100, 100, 100, 100, 100, 100, 100, 100,
├ 500, 100, 100, 100, 100, 100
├ 500, 100, 100, 100, 100, 50, 50
└ 500, 100, 100, 100, 100, 50, 10, 10, 10, 10, 10

引用「プログラマ脳を鍛える数学パズル　著者長井敏克」

回答

answer_1.py

cnt = 0
for coin500 in range(0, 3):
    for coin100 in range(0, 11):
        for coin50 in range(0, 16):
            for coin10 in range(0, 16):
                if coin500 + coin100 + coin50 + coin10 <= 15:
                    if coin500 * 500 + coin100 * 100 + coin50 * 50 + coin10 * 10 == 1000:
                        cnt += 1

print(cnt)    # 20

answer_2.py

import itertools

coins = [10, 50, 100, 500]
cnt = 0

for i in range(2, 16):
    for coin_set in itertools.combinations_with_replacement(coins, i):
        if sum(coin_set) == 1000:
            cnt += 1

print(cnt)    # 20

answer_3.py

import copy
cnt = 0

def change(target, coins, usable):
    coin = coins.pop(0)
    if len(coins) == 0:
        if target / coin <= usable:
            global cnt
            cnt += 1
    else:
        for i in range(0, int(target / coin + 1)):
            change(target - coin * i, copy.copy(coins), usable - i)

change(1000, [500, 100, 50, 10], 15)
print(cnt)    # 20

つまづいたところ

今回の問題はスムーズに解けたような気がしますね。

はじめのanswer_1.pyが1000円となる小銭とその枚数を単純に繰り返し求めています。
次のanswer_2.pyでは、1000円札や2000円札、5000円札を使うこと、
1万円との両替なども考慮した拡張性のあるものとなっています。
最後のanswer_3.pyではさらに再帰も使ったものになっています。

特徴として、
answer_1では、500円から順に0枚から各小銭の最大使用枚数まで、
for文をひたすら回しまくっていますね。
金額を変更するとその分for文を追加／変更したりなど拡張性に乏しいです。

answer_2.pyでは、itertoolsモジュールを使用しています。
for coin_set in itertools.combinations_with_replacement(coins, i):で、
変数coin_setの中には配列coinsからi個の要素を使ったタプル型が返されます。
例えばi = 2の時、(10, 10), (10, 50), (10, 100),・・・のように
配列coinsの中から2個の要素を使ったタプル型が返されます。
この時、(10, 10)のように要素の重複があるものも返されます。
あとはsum関数を使い、タプルの要素を足した合計数が1000となった時だけ、
変数cntに1を加えます。

answer_3.pyでは、copyモジュールを使用しています。
再帰の時に引数coinsに渡す際にcopyを使っています。
これは再帰が実行されることによって、
関数change中のcoins、for文に影響を与えないようにしているのかなーと思います・・・
自信ないです、すみません。

スムーズに解けたわりには締まらない終わり方となってしまいましたが、
ご拝読ありがとうございました。

Python いまだに現金払い？

問題

回答

つまづいたところ