sumoch1メモ

記録に残したいことを書いていきます。文章力はないです。

「1000円分の切手を買ってきて」とお願いされた時の買い方のパターンの総数を計算するプログラム(Python)

このツイートを見てプログラムを作って計算してみました。

初心者なので計算が合っているか保証できません。
間違ってたら誰か教えてください。

再帰を使ったアルゴリズムで計算します。
x円で買うことが出来るパターンの総数をf(x)とします。f(0)=1とします。

残金がx円の時、x円以下の切手(値段p)を選びf(x-p)を足します。これを繰り返します。
 この時(1,2)と(2,1)などの重複をカウントしないために高い切手から順に買います。前の試行で買った切手y円より高い切手を買わないようにします。
このためf(x,y)を「y円以下の切手でx円分買う時の組み合わせの総数」として再帰的に計算を行います。

再帰的に計算することで計算量が莫大になるためメモ化再帰を使います。
https://qiita.com/alchemist/items/c75174c41b0bcd31ecc6

from functools import lru_cache
price_list = [1, 2, 3, 5, 10, 20, 30, 50, 62, 82,
              92, 100, 120, 140, 205, 280, 310, 500, 1000]
price_list = price_list[::-1] #降順にする

@lru_cache(maxsize=10000)
def count(x, y):
    if x < 2:
        return 1
    else:
        sum_price = 0
        for p in price_list:
            if x-p >= 0 and p <= y:
                sum_price += count(x-p, p)
        return sum_price

print(count(1000,1000)


計算結果は
1141266126310
1兆通り以上あるらしいです。
間違っていたらこちらまでご連絡ください↓
もち (@sumoch1) | Twitter