Asi*_*sif 0 php arrays algorithm
一般流通中有八个硬币:
1p,2p,5p,10p,20p,50p,$ 1(100p)和$ 2(200p).
可以通过以下方式赚2美元:1x $ 1 + 1x50p + 2x20p + 1x5p + 1x2p + 3x1p
使用任意数量的硬币可以用3种不同的方式制作3美元？
我们怎样才能用PHP做到这一点？
使用生成函数可以最好地解决此问题和类似问题.
对于这种情况,您需要考虑表单的条款
1/(1 - x^k) = 1 + x^k + x^(2k) + x^(3k) + ...
其中k一个值1p, 2p, 5p, 10p, 20p, 50p, 100p, 200p.现在将所有这8个术语相乘得到
f(x) = 1 / [ (1-x) * (1-x^2) * (1-x^5) * ... * (1-x^200) ]
然后,系数x^m恰好mp是给定面额的方式数.例如,系数x^200是6,这对应于从给定面额中6获得确切方法的事实200p = $2.
这是一个快速而肮脏的解释为什么这个工作.x^min 的系数f(x)是x^(i*k)从(1 - x^k)分母中的形式的每个线性因子中获取形式的一个项的方式的数量,以便指数的总和是m,即
i1*k1 + i2*k2 + ... + i8*k8 = m
现在,术语k1 = 1对应于取1p,术语k2 = 2对应于取2p,术语k3=5p对应于取5p,等等.上面的总和变成了
i1*(1p) + i2*(2p) + i3*(5p) + ... + i8*(200p) = m
它给出了每个面额的金额.