小明家里有三个存钱罐
第一个里面全是$1面值硬币
第二个里面全是$2面值硬币
第三个里面全是$5面值硬币
鉴于小明是土豪,每个存钱罐里面的硬币数量为无穷多
妈妈今天想吃龙虾,小明在中国店称了一颗龙虾要$37,请问
1. 有多少种硬币组合办法可以刚好凑出$37
2. 任意价格$x的商品,怎么找出有多少种硬币组合办法(a,b,c) such that a*$1 + b*$2 + c*$5 = $x
小明买菜
版主: verdelite, Tlexander
-
- 著名点评
- 帖子: 4585
- 注册时间: 8月 21, 2022, 2:20 pm
Re: 小明买菜
用a_n表示可以用某种硬币凑出$n总数的组合的数量。如果只用$1硬币,其对应的母函数为
1/(1-x) = 1 + x + x^2 + ... = a_0 * 1 + a_1 * x + a_2 * x^2 + ...
如果只用$2硬币,其对应的母函数为
1/(1-x^2) = 1 + x^2 + x^4 + ... = a_0 * 1 + a_1 * x^2 + a_2 * x^4 + ...
只用$5硬币同理
那么对于任意价格$x的商品,只需要检查\frac{1}{(1-x)(1-x^2)(1-x^5)}泰勒展开后对应x^n项的系数,其up to x^40的展开式为
92*x^39 + 88*x^38 + 84*x^37 + 80*x^36 + 76*x^35 + 72*x^34 + 68*x^33 + 65*x^32 + 61*x^31 + 58*x^30 + 54*x^29 + 51*x^28 + 48*x^27 + 45*x^26 + 42*x^25 + 39*x^24 + 36*x^23 + 34*x^22 + 31*x^21 + 29*x^20 + 26*x^19 + 24*x^18 + 22*x^17 + 20*x^16 + 18*x^15 + 16*x^14 + 14*x^13 + 13*x^12 + 11*x^11 + 10*x^10 + 8*x^9 + 7*x^8 + 6*x^7 + 5*x^6 + 4*x^5 + 3*x^4 + 2*x^3 + 2*x^2 + x + 1
所以付$37有84种办法
1/(1-x) = 1 + x + x^2 + ... = a_0 * 1 + a_1 * x + a_2 * x^2 + ...
如果只用$2硬币,其对应的母函数为
1/(1-x^2) = 1 + x^2 + x^4 + ... = a_0 * 1 + a_1 * x^2 + a_2 * x^4 + ...
只用$5硬币同理
那么对于任意价格$x的商品,只需要检查\frac{1}{(1-x)(1-x^2)(1-x^5)}泰勒展开后对应x^n项的系数,其up to x^40的展开式为
92*x^39 + 88*x^38 + 84*x^37 + 80*x^36 + 76*x^35 + 72*x^34 + 68*x^33 + 65*x^32 + 61*x^31 + 58*x^30 + 54*x^29 + 51*x^28 + 48*x^27 + 45*x^26 + 42*x^25 + 39*x^24 + 36*x^23 + 34*x^22 + 31*x^21 + 29*x^20 + 26*x^19 + 24*x^18 + 22*x^17 + 20*x^16 + 18*x^15 + 16*x^14 + 14*x^13 + 13*x^12 + 11*x^11 + 10*x^10 + 8*x^9 + 7*x^8 + 6*x^7 + 5*x^6 + 4*x^5 + 3*x^4 + 2*x^3 + 2*x^2 + x + 1
所以付$37有84种办法