どのように多くの異なるコインを使用して$ 3を作ることができますか？

Question

一般的に8つの硬貨があります。

1p、2p、5p、10p、20p、50p、$ 1（100p）、$ 2（200p）です。

次のように$ 2にすることができる： 1X $ 1 + 1x50p + 2x20p + 1x5p + 1x2p + 3x1p

コインの任意の番号を使用して$ 3行うことができますどのように多くの異なる方法？

PHPを使用してどのようにすることができますか？

Answer 1

この問題とそのような問題は、generating functionsを使用して解決するのが最も効果的です。

は、このような場合のために、フォームkは値1p, 2p, 5p, 10p, 20p, 50p, 100p, 200pの一つである

1/(1 - x^k) = 1 + x^k + x^(2k) + x^(3k) + ... 

の条件を検討したいです。今

f(x) = 1/[ (1-x) * (1-x^2) * (1-x^5) * ... * (1-x^200) ] 

が続い x^mの係数を正確に特定宗派から作ることができる mpいくつかの方法で取得するために一緒にこれらの8項の全てを掛けます。例えば、 x^200の係数は 6であり、これは正確に 6の与えられた金種から得ることができるという事実に対応する。

---

ここでは、これがなぜ機能するのかについて、すばやく説明します。指数の合計が今、すなわち

i1*k1 + i2*k2 + ... + i8*k8 = m 

mなるようにf(x)でx^mの係数は、分母形態(1 - x^k)の各線形係数からフォームの用語を取るために、いくつかの方法でありますk1 = 1の語は1pと一致し、k2 = 2の語は2pの語に相当し、k3=5pの語は5pという語に相当する。上記の合計は

i1*(1p) + i2*(2p) + i3*(5p) + ... + i8*(200p) = m 

となり、各金種の金額を示します。