読者です 読者をやめる 読者になる 読者になる

千円札、五百円、百円硬貨を使って3000円を支払う方法は何通りあるか

問題 Python

detail.chiebukuro.yahoo.co.jp

d.hatena.ne.jp

順列(再帰

def perm(head, money):

    coin = [100, 500, 1000]

    if money == 0:

        return [head]

    else:

        res = []

        for i in coin:

            if money - i < 0:
                break

            headx = head + [i]

            res += perm(headx, money - i)

        return res

# 3000円になる順列作成
data = perm([], 3000)
# print(len(data))

# リスト内ソート、重複除去
tp = set(map(tuple, map(sorted, data)))

print(len(tp))

順列(再帰2)

100×5にして回数減らす

def perm(head, money):

    coin = [100 * 5, 500, 1000]


    if money == 0:

        return [head]

    else:

        res = []

        for i, j in enumerate(coin):

            if money - j < 0:
                break

            headx = head + [j] if i else head + [100] * 5

            res += perm(headx, money - j)

        return res

# 3000円になる順列作成
data = perm([], 3000)
print(len(data))

# リスト内ソート、重複除去
tp = set(map(tuple, map(sorted, data)))

print(len(tp))

組合せ

1000円の組合せ

  1. 1000
  2. 500×2
  3. 500・100×5
  4. 100×10

1~4の組合せを作成

10.1. itertools — 効率的なループ実行のためのイテレータ生成関数 — Python 3.5.2 ドキュメント

  • 組合せ重複あり

combinations_with_replacement()

import itertools

# 組合せ作成後、リスト平坦化
data =[ sum(i, []) for i in itertools.combinations_with_replacement([[1000],[500,500],[500]+[100]*5,[100]*10], 3)]

# リスト内ソート、重複除去
tp = set(map(tuple, map(sorted, data)))

print(len(tp))