珍珠湾ART

标题: 硬币问题 [打印本页]

作者: xyh    时间: 2012-5-22 03:45
标题: 硬币问题

硬币有1分, 5分, 10分, 25分四种.

问有多少种不同的方法可以凑成 2 元.

例如:

方法一: 200个1分

方法二: 195个1分, 1个5分.

...

www.ddhw.com

 


作者: 感谢上帝让我们还活着    时间: 2012-5-22 16:15
标题: 回复:硬币问题

有 1463 种不同的方法。


 

作者: 你哦body    时间: 2012-5-22 16:35
标题: 很惊奇有人对此感兴趣。可以理解。但忍不住想说吃饱了撑的

  很惊奇有人对此感兴趣。可以理解。但忍不住想说吃饱了撑的





作者: 感谢上帝让我们还活着    时间: 2012-5-23 01:22
标题: 回复:很惊奇有人对此感兴趣。可以理解。但忍不住想说吃饱了撑的

编号          1分           5分          10分         25分
-------------------------------------------------------------
 1             0             0             0             8
 2             0             0             5             6
 3             0             0             10            4
 4             0             0             15            2
 5             0             0             20            0
 6             0             1             2             7
 7             0             1             7             5
 8             0             1             12            3
 9             0             1             17            1
 10            0             2             4             6
 11            0             2             9             4
 12            0             2             14            2
 13            0             2             19            0
 14            0             3             1             7
 15            0             3             6             5
 16            0             3             11            3
 17            0             3             16            1
 18            0             4             3             6
 19            0             4             8             4
 20            0             4             13            2
 21            0             4             18            0
 22            0             5             0             7
 23            0             5             5             5
 24            0             5             10            3
 25            0             5             15            1
 26            0             6             2             6
 27            0             6             7             4
 28            0             6             12            2
 29            0             6             17            0
 30            0             7             4             5
 31            0             7             9             3
 32            0             7             14            1
 33            0             8             1             6
 34            0             8             6             4
 35            0             8             11            2
 36            0             8             16            0
 37            0             9             3             5
 38            0             9             8             3
 39            0             9             13            1
 40            0             10            0             6
 41            0             10            5             4
 42            0             10            10            2
 43            0             10            15            0
 44            0             11            2             5
 45            0             11            7             3
 46            0             11            12            1
 47            0             12            4             4
 48            0             12            9             2
 49            0             12            14            0
 50            0             13            1             5
 51            0             13            6             3
 52            0             13            11            1
 53            0             14            3             4
 54            0             14            8             2
 55            0             14            13            0
 56            0             15            0             5
 57            0             15            5             3
 58            0             15            10            1
 59            0             16            2             4
 60            0             16            7             2
 61            0             16            12            0
 62            0             17            4             3
 63            0             17            9             1
 64            0             18            1             4
 65            0             18            6             2
 66            0             18            11            0
 67            0             19            3             3
 68            0             19            8             1
 69            0             20            0             4
 70            0             20            5             2
 71            0             20            10            0
 72            0             21            2             3
 73            0             21            7             1
 74            0             22            4             2
 75            0             22            9             0
 76            0             23            1             3
 77            0             23            6             1
 78            0             24            3             2
 79            0             24            8             0
 80            0             25            0             3
 81            0             25            5             1
 82            0             26            2             2
 83            0             26            7             0
 84            0             27            4             1
 85            0             28            1             2
 86            0             28            6             0
 87            0             29            3             1
 88            0             30            0             2
 89            0             30            5             0
 90            0             31            2             1
 91            0             32            4             0
 92            0             33            1             1
 93            0             34            3             0
 94            0             35            0             1
 95            0             36            2             0
 96            0             38            1             0
 97            0             40            0             0
 98            5             0             2             7
 99            5             0             7             5
 100           5             0             12            3
 101           5             0             17            1
 102           5             1             4             6
 103           5             1             9             4
 104           5             1             14            2
 105           5             1             19            0
 106           5             2             1             7
 107           5             2             6             5
 108           5             2             11            3
 109           5             2             16            1
 110           5             3             3             6
 111           5             3             8             4
 112           5             3             13            2
 113           5             3             18            0
 114           5             4             0             7
 115           5             4             5             5
 116           5             4             10            3
 117           5             4             15            1
 118           5             5             2             6
 119           5             5             7             4
 120           5             5             12            2
 121           5             5             17            0
 122           5             6             4             5
 123           5             6             9             3
 124           5             6             14            1
 125           5             7             1             6
 126           5             7             6             4
 127           5             7             11            2
 128           5             7             16            0
 129           5             8             3             5
 130           5             8             8             3
 131           5             8             13            1
 132           5             9             0             6
 133           5             9             5             4
 134           5             9             10            2
 135           5             9             15            0
 136           5             10            2             5
 137           5             10            7             3
 138           5             10            12            1
 139           5             11            4             4
 140           5             11            9             2
 141           5             11            14            0
 142           5             12            1             5
 143           5             12            6             3
 144           5             12            11            1
 145           5             13            3             4
 146           5             13            8             2
 147           5             13            13            0
 148           5             14            0             5
 149           5             14            5             3
 150           5             14            10            1
 151           5             15            2             4
 152           5             15            7             2
 153           5             15            12            0
 154           5             16            4             3
 155           5             16            9             1
 156           5             17            1             4
 157           5             17            6             2
 158           5             17            11            0
 159           5             18            3             3
 160           5             18            8             1
 161           5             19            0             4
 162           5             19            5             2
 163           5             19            10            0
 164           5             20            2             3
 165           5             20            7             1
 166           5             21            4             2
 167           5             21            9             0
 168           5             22            1             3
 169           5             22            6             1
 170           5             23            3             2
 171           5             23            8             0
 172           5             24            0             3
 173           5             24            5             1
 174           5             25            2             2
 175           5             25            7             0
 176           5             26            4             1
 177           5             27            1             2
 178           5             27            6             0
 179           5             28            3             1
 180           5             29            0             2
 181           5             29            5             0
 182           5             30            2             1
 183           5             31            4             0
 184           5             32            1             1
 185           5             33            3             0
 186           5             34            0             1
 187           5             35            2             0
 188           5             37            1             0
 189           5             39            0             0
 190           10            0             4             6
 191           10            0             9             4
 192           10            0             14            2
 193           10            0             19            0
 194           10            1             1             7
 195           10            1             6             5
 196           10            1             11            3
 197           10            1             16            1
 198           10            2             3             6
 199           10            2             8             4
 200           10            2             13            2
 201           10            2             18            0
 202           10            3             0             7
 203           10            3             5             5
 204           10            3             10            3
 205           10            3             15            1
 206           10            4             2             6
 207           10            4             7             4
 208           10            4             12            2
 209           10            4             17            0
 210           10            5             4             5
 211           10            5             9             3
 212           10            5             14            1
 213           10            6             1             6
 214           10            6             6             4
 215           10            6             11            2
 216           10            6             16            0
 217           10            7             3             5
 218           10            7             8             3
 219           10            7             13            1
 220           10            8             0             6
 221           10            8             5             4
 222           10            8             10            2
 223           10            8             15            0
 224           10            9             2             5
 225           10            9             7             3
 226           10            9             12            1
 227           10            10            4             4
 228           10            10            9             2
 229           10            10            14            0
 230           10            11            1             5
 231           10            11            6             3
 232           10            11            11            1
 233           10            12            3             4
 234           10            12            8             2
 235           10            12            13            0
 236           10            13            0             5
 237           10            13            5             3
 238           10            13            10            1
 239           10            14            2             4
 240           10            14            7             2
 241           10            14            12            0
 242           10            15            4             3
 243           10            15            9             1
 244           10            16            1             4
 245           10            16            6             2
 246           10            16            11            0
 247           10            17            3             3
 248           10            17            8             1
 249           10            18            0             4
 250           10            18            5             2
 251           10            18            10            0
 252           10            19            2             3
 253           10            19            7             1
 254           10            20            4             2
 255           10            20            9             0
 256           10            21            1             3
 257           10            21            6             1
 258           10            22            3             2
 259           10            22            8             0
 260           10            23            0             3
 261           10            23            5             1
 262           10            24            2             2
 263           10            24            7             0
 264           10            25            4             1
 265           10            26            1             2
 266           10            26            6             0
 267           10            27            3             1
 268           10            28            0             2
 269           10            28            5             0
 270           10            29            2             1
 271           10            30            4             0
 272           10            31            1             1
 273           10            32            3             0
 274           10            33            0             1
 275           10            34            2             0
 276           10            36            1             0
 277           10            38            0             0
 278           15            0             1             7
 279           15            0             6             5
 280           15            0             11            3
 281           15            0             16            1
 282           15            1             3             6
 283           15            1             8             4
 284           15            1             13            2
 285           15            1             18            0
 286           15            2             0             7
 287           15            2             5             5
 288           15            2             10            3
 289           15            2             15            1
 290           15            3             2             6
 291           15            3             7             4
 292           15            3             12            2
 293           15            3             17            0
 294           15            4             4             5
 295           15            4             9             3
 296           15            4             14            1
 297           15            5             1             6
 298           15            5             6             4
 299           15            5             11            2
 300           15            5             16            0
 301           15            6             3             5
 302           15            6             8             3
 303           15            6             13            1
 304           15            7             0             6
 305           15            7             5             4
 306           15            7             10            2
 307           15            7             15            0
 308           15            8             2             5
 309           15            8             7             3
 310           15            8             12            1
 311           15            9             4             4
 312           15            9             9             2
 313           15            9             14            0
 314           15            10            1             5
 315           15            10            6             3
 316           15            10            11            1
 317           15            11            3             4
 318           15            11            8             2
 319           15            11            13            0
 320           15            12            0             5
 321           15            12            5             3
 322           15            12            10            1
 323           15            13            2             4
 324           15            13            7             2
 325           15            13            12            0
 326           15            14            4             3
 327           15            14            9             1
 328           15            15            1             4
 329           15            15            6             2
 330           15            15            11            0
 331           15            16            3             3
 332           15            16            8             1
 333           15            17            0             4
 334           15            17            5             2
 335           15            17            10            0
 336           15            18            2             3
 337           15            18            7             1
 338           15            19            4             2
 339           15            19            9             0
 340           15            20            1             3
 341           15            20            6             1
 342           15            21            3             2
 343           15            21            8             0
 344           15            22            0             3
 345           15            22            5             1
 346           15            23            2             2
 347           15            23            7             0
 348           15            24            4             1
 349           15            25            1             2
 350           15            25            6             0
 351           15            26            3             1
 352           15            27            0             2
 353           15            27            5             0
 354           15            28            2             1
 355           15            29            4             0
 356           15            30            1             1
 357           15            31            3             0
 358           15            32            0             1
 359           15            33            2             0
 360           15            35            1             0
 361           15            37            0             0
 362           20            0             3             6
 363           20            0             8             4
 364           20            0             13            2
 365           20            0             18            0
 366           20            1             0             7
 367           20            1             5             5
 368           20            1             10            3
 369           20            1             15            1
 370           20            2             2             6
 371           20            2             7             4
 372           20            2             12            2
 373           20            2             17            0
 374           20            3             4             5
 375           20            3             9             3
 376           20            3             14            1
 377           20            4             1             6
 378           20            4             6             4
 379           20            4             11            2
 380           20            4             16            0
 381           20            5             3             5
 382           20            5             8             3
 383           20            5             13            1
 384           20            6             0             6
 385           20            6             5             4
 386           20            6             10            2
 387           20            6             15            0
 388           20            7             2             5
 389           20            7             7             3
 390           20            7             12            1
 391           20            8             4             4
 392           20            8             9             2
 393           20            8             14            0
 394           20            9             1             5
 395           20            9             6             3
 396           20            9             11            1
 397           20            10            3             4
 398           20            10            8             2
 399           20            10            13            0
 400           20            11            0             5
 401           20            11            5             3
 402           20            11            10            1
 403           20            12            2             4
 404           20            12            7             2
 405           20            12            12            0
 406           20            13            4             3
 407           20            13            9             1
 408           20            14            1             4
 409           20            14            6             2
 410           20            14            11            0
 411           20            15            3             3
 412           20            15            8             1
 413           20            16            0             4
 414           20            16            5             2
 415           20            16            10            0
 416           20            17            2             3
 417           20            17            7             1
 418           20            18            4             2
 419           20            18            9             0
 420           20            19            1             3
 421           20            19            6             1
 422           20            20            3             2
 423           20            20            8             0
 424           20            21            0             3
 425           20            21            5             1
 426           20            22            2             2
 427           20            22            7             0
 428           20            23            4             1
 429           20            24            1             2
 430           20            24            6             0
 431           20            25            3             1
 432           20            26            0             2
 433           20            26            5             0
 434           20            27            2             1
 435           20            28            4             0
 436           20            29            1             1
 437           20            30            3             0
 438           20            31            0             1
 439           20            32            2             0
 440           20            34            1             0
 441           20            36            0             0
 442           25            0             0             7
 443           25            0             5             5
 444           25            0             10            3
 445           25            0             15            1
 446           25            1             2             6
 447           25            1             7             4
 448           25            1             12            2
 449           25            1             17            0
 450           25            2             4             5
 451           25            2             9             3
 452           25            2             14            1
 453           25            3             1             6
 454           25            3             6             4
 455           25            3             11            2
 456           25            3             16            0
 457           25            4             3             5
 458           25            4             8             3
 459           25            4             13            1
 460           25            5             0             6
 461           25            5             5             4
 462           25            5             10            2
 463           25            5             15            0
 464           25            6             2             5
 465           25            6             7             3
 466           25            6             12            1
 467           25            7             4             4
 468           25            7             9             2
 469           25            7             14            0
 470           25            8             1             5
 471           25            8             6             3
 472           25            8             11            1
 473           25            9             3             4
 474           25            9             8             2
 475           25            9             13            0
 476           25            10            0             5
 477           25            10            5             3
 478           25            10            10            1
 479           25            11            2             4
 480           25            11            7             2
 481           25            11            12            0
 482           25            12            4             3
 483           25            12            9             1
 484           25            13            1             4
 485           25            13            6             2
 486           25            13            11            0
 487           25            14            3             3
 488           25            14            8             1
 489           25            15            0             4
 490           25            15            5             2
 491           25            15            10            0
 492           25            16            2             3
 493           25            16            7             1
 494           25            17            4             2
 495           25            17            9             0
 496           25            18            1             3
 497           25            18            6             1
 498           25            19            3             2
 499           25            19            8             0
 500           25            20            0             3
 501           25            20            5             1
 502           25            21            2             2
 503           25            21            7             0
 504           25            22            4             1
 505           25            23            1             2
 506           25            23            6             0
 507           25            24            3             1
 508           25            25            0             2
 509           25            25            5             0
 510           25            26            2             1
 511           25            27            4             0
 512           25            28            1             1
 513           25            29            3             0
 514           25            30            0             1
 515           25            31            2             0
 516           25            33            1             0
 517           25            35            0             0
 518           30            0             2             6
 519           30            0             7             4
 520           30            0             12            2
 521           30            0             17            0
 522           30            1             4             5
 523           30            1             9             3
 524           30            1             14            1
 525           30            2             1             6
 526           30            2             6             4
 527           30            2             11            2
 528           30            2             16            0
 529           30            3             3             5
 530           30            3             8             3
 531           30            3             13            1
 532           30            4             0             6
 533           30            4             5             4
 534           30            4             10            2
 535           30            4             15            0
 536           30            5             2             5
 537           30            5             7             3
 538           30            5             12            1
 539           30            6             4             4
 540           30            6             9             2
 541           30            6             14            0
 542           30            7             1             5
 543           30            7             6             3
 544           30            7             11            1
 545           30            8             3             4
 546           30            8             8             2
 547           30            8             13            0
 548           30            9             0             5
 549           30            9             5             3
 550           30            9             10            1
 551           30            10            2             4
 552           30            10            7             2
 553           30            10            12            0
 554           30            11            4             3
 555           30            11            9             1
 556           30            12            1             4
 557           30            12            6             2
 558           30            12            11            0
 559           30            13            3             3
 560           30            13            8             1
 561           30            14            0             4
 562           30            14            5             2
 563           30            14            10            0
 564           30            15            2             3
 565   
作者: xyh    时间: 2012-5-24 18:22
标题: 写程序算出来的吧?

  写程序算出来的吧?





作者: 感谢上帝让我们还活着    时间: 2012-5-24 19:53
标题: 回复:写程序算出来的吧?

对。和您的答案相同吗?另外,算不算违反您的规则?
www.ddhw.com

 

作者: xyh    时间: 2012-5-24 21:06
标题: 当然算违反规则[:-M]

  当然算违反规则





作者: 感谢上帝让我们还活着    时间: 2012-5-25 03:14
标题: 回复:当然算违反规则

呵呵,编程的好处是那个说我吃饱了撑的朋友不吭声了,新用户也有点扫兴了。
www.ddhw.com

 

作者: 天涯浪子    时间: 2012-5-25 04:22
标题: 您'问有多少种不同的方法可以凑成2元' 没说用硬币 咱正好有张$2纸币[:-M]

  您'问有多少种不同的方法可以凑成2元' 没说用硬币 咱正好有张$2纸币





作者: 括号1    时间: 2012-5-27 08:35
标题: 回复:硬币问题

答案是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

答案为1463。
www.ddhw.com

 





欢迎光临 珍珠湾ART (http://zzwav.com/) Powered by Discuz! X3