硬币问题

括号1

答案是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项的系数 http://www.wolframalpha.com/input/?i=d%5E40%2Fdx%5E40%281%2F%28%281-x%29%5E2%281-x%5E2%29%281-x%5E5%2940%21%29%29%3Bx%3D0 答案为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 答案为1463。 www.ddhw.com