答案是1463。提供3种不同的解法。
#### 方法1，枚举法: 原题要求的是下列方程的解的总数：
PENNY+5*NICKEL+10*DIME+25*QUARTER = 200。
考虑PENNY是5的整数倍，令PENNY=5P，NICKEL=N，DIME=D， QUARTER=Q，原题可以等价与下列方程解的个数：
P + N + 2*D + 5*Q = 40
分别看Q=0，1，2，3，4，5，6，7，8的情况，用标准的隔板法算有：
C(22, 2) + C(21, 2) // Q = 0 + 2*C(19, 2) // Q = 1 + C(17, 2) + C(16, 2) // Q = 2 + 2*C(14, 2) // Q = 3 + C(12, 2) + C(11, 2) // Q = 4 + 2*C(9, 2) // Q = 5 + C(7, 2) + C(6, 2) // Q = 6 + 2*C(4, 2) // Q = 7 + 1 // Q = 8 = 21^2 + 19*18 + 16^2 + 14*13 + 11^2 + 9*8 + 6^2 + 4*3 + 1 = 1463
#### 方法2，生成函数方法
g(x) = 1/((1-x)*(1-x^5)*(1-x^10)*(1-x^25))
考虑到PENNY的个数一定是5的整数倍，令z=x^5，可得等价的生成函数。
g(z) = 1/((1-z)^2(1-z^2)(1-z^5))
上WOLFRAMALPHA求该函数展开z^40项的系数
答案为1463。
#### 方法3，编程 count = 0; for penny in range(0,201): for nickel in range(0,41): for dime in range(0,21): for quarter in range(0,9): total = penny + 5*nickel + 10*dime + 25*quarter if total == 200: count += 1 print count, [penny, nickel, dime, quarter] break if total > 200: break
|
哈哈哈哈 O(∩_∩)O哈哈~ 好久不来了，不小心看了一眼自己主页，发现自动关联了自己以往发过的帖，点进这个看了一眼，笑个半死。。。敢情我当初还发过这么搞笑的东西啊，我自己完全不记得了 
雷达卡
发表于 2012-5-22 03:45:38
收藏
分享
支持
反对
置顶卡
千斤顶
楼主