前回は母関数からSagemathを用いていくつかの問題を解きましたが、Sagemathを動かす環境はかなり限られているので、Pythonで解くコードに変換します。
基本的には多項式の掛け算となるので、多項式の係数をリストとしてnumpyのconvolveを使って実装しました。
両替問題を解く
まず「1p,2p,5pコインを使って5pにするのは何通りあるか求めよ」を考えると以下の多項式を計算して$x^5$の係数が答えでした。
(1 + x + x^{2} + x^{3} + x^{4} + x^{5}) \times
(1 + x^{2} + x^{4} ) \times
(1 + x^{5})
多項式の係数のリストの畳み込みを$*$で表すと、以下のような計算をしていつも最初の６個だけを残せば、リストの最後に答えの４が求まります。
\begin{align}
&[1,1,1,1,1,1] * [1,0,1,0,1,0] * [1,0,0,0,0,1] \\
& = [1,1,2,2,3,4]
\end{align}
この畳み込みにはnumpyのconvolveが使えるので、前回の例題は以下のようなコードになりました。
【Project Euler】Problem 31: コインの合計
問題の要約：1p,2p,5p,10p,20p,50p,£1(100p),£2(200p)のコインを使って£2(200p)にするのは何通りあるか求めよ
import numpy as np
N, coins = 200, [1,2,5,10,20,50,100,200]
p = [1]
for c in coins:
p = np.convolve(p, [1 if i % c == 0 else 0 for i in range(N+1)])[:N+1]
print(f"Answer: {p[N]}")
# Answer: 73682
他の例題も同様に変換できます。
両替問題を解く（個数制限あり）
問題の要約： 1p,2p,5p,10p,20p,50p,£1(100p),£2(200p)のコインを使って£2(200p)にするのは何通りあるか求めよ。ただし1p,2p,5pは10個までしか使えない。
N, coins = 200, [(1,10),(2,10),(5,10),(10,0),(20,0),(50,0),(100,0),(200,0)]
p = [1]
for (c, m) in coins:
p = np.convolve(p,[1 if i % c == 0 else 0 for i in range((N if m==0 else m*c)+1)])[:N+1]
print(f"Answer: {p[N]}")
# Answer: 3481
分割問題を解く
【Project Euler】Problem 76: 整数の分割
問題の要約：100を自然数の和で何通りの組み合わせで表せるかを求めよ
N = 100
p = [1]
for n in range(1,N+1):
p = np.convolve(p,[1 if i % n == 0 else 0 for i in range(N+1)])[:N+1]
print(f"Answer: {p[N]}")
# Answer: 190569292
（開発環境：Google Colab）