1, 2, 5, 10, 20, 50, 100, 200 だけを使って 500 を作る方法が何通りあるか知りたい.次の方法でそれを実行できるようにしたい:
あるセット T からの数のみを使用して、与えられた数 n の整数パーティションの数は、すべての (1-x t ) -1の積の x n項の係数から取得できます。ここで、t は T 内にあります。 .
これを行うには、(1-x t ) -1のテイラー展開が (1+x t +x 2t +...)に等しいことに注意してください。これまでに書いたコードは次のとおりです。
#################################
# First, define a function that returns the product of two
# polynomials. A list here
# represents a polynomial with the entry in a list corresponding to
# the coefficient of the power of x associated to that position, e.g.
# [1,2,3] = 1 + 2x + 3x^2.
#################################
def p(a,v):
"""(list,list) -> list"""
prodav = [0]*(len(a)+len(v)-1)
for n in range(len(a)):
for m in range(len(v)):
prodav[n+m] += v[m]*a[n]
return prodav
#################################
# Now, let a,b,c,...,h represent the first 501 terms in the Taylor
# expansion of 1/(1-x^n), where n gives the coin value, i.e
# 1,2,5,10,20,50,100,200 in pence. See the generating function
# section in https://en.wikipedia.org/wiki/Partition_(number_theory).
# Our function, p, multiplies all these polynomials together
# (when applied iteratively). As per the Wiki entry, the coefficient
# of x^t is equal to the number of possible ways t can be made,
# using only the denominations of change available, a so called
# 'restricted integer partition'. Note that it isn't necessary to
# consider the entire Taylor expansion since we only need the
# 500th power.
#################################
a = ( [1] ) * 501 # 1
b = ( [1] + [0] ) * 250 + [1] # 2
c = ( [1] + [0]*4 ) * 100 + [1] # 5
d = ( [1] + [0]*9 ) * 50 + [1] # 10
e = ( [1] + [0]*19 ) * 25 + [1] # 20
f = ( [1] + [0]*49 ) * 10 + [1] # 50
g = ( [1] + [0]*99 ) * 5 + [1] # 100
h = ( [1] + [0]*199 ) * 2 + [0]*101 # 200
x = p(h,p(g,p(f,p(e,p(d,p(c,p(b,a)))))))
print(x[500]) # = 6290871
私の問題は、これが与える答えが正しいと確信していないことです。私はそれを、出力が互いに一致する他の 2 つの貪欲なアルゴリズムと比較しましたが、私のものではありません。私がどこで間違ったのか誰にもわかりますか？