趣味数学028：换零钱问题

趣味数学028：换零钱问 换零钱问题 换零钱这样的事，在日常生活中经常会遇到。以整元纸币为例，有1元、5元、10元、20元、50元、100元6种，换零钱就是把面额大的换成面额小的。也许你已经换过无数次，不过，你可曾想过换零钱的究竟有多少种吗,也许没有想过，其实，这里面的学问大着呢。今天我们就来研究研究这个司空见惯的问题。 对于面额比较小的，很容易把所有的方法一一列举出来，比如: 把一张5元的换成面额较小的，只有5张1元的1种方法; 把一张10元的换成面额较小的，有2张5元的、1张5元的5张1元的、10张1元的，3种方法; 把一张20元的换成面额较小的，有2张10元的、1张10元的2张5元的、1张10元的1张5元的5张1元的、4张5元的、3张5元的5张1元的、2张5元的10张1元的、1张5元的15张1元的、20张1元的，8种方法。 那么， 把一张50元的换成面额较小的有多少种方法, 把一张100元的换成面额较小的有多少种方法, 虽然你会想到答案肯定比8种更多，但是你一定想不到，答案竟然会分别达到56种和343种。不信请往下看: 先看第一个问题:把一张50元的换成面额较小的有多少种方法, 为了便于有序思考，避免发生重复或遗漏，仍然采用列举的方法。 方法序号 20元 10元 5元 1元 (单位:张) 1 2 1 0 0 2 2 0 2 0 3 2 0 1 5 4 2 0 0 10 5 1 3 0 0 6 1 2 2 0 7 1 2 1 5 8 1 2 0 10 9 1 1 4 0 10 1 1 3 5 11 1 1 2 10 1 12 1 1 1 15 13 1 1 0 20 14 1 0 6 0 15 1 0 5 5 16 1 0 4 10 17 1 0 3 15 18 1 0 2 20 19 1 0 1 25 20 1 0 0 30 21 0 5 0 0 22 0 4 2 0 23 0 4 1 5 24 0 4 0 10 25 0 3 4 0 26 0 3 3 5 27 0 3 2 10 28 0 3 1 15 29 0 3 0 20 30 0 2 6 0 31 0 2 5 5 32 0 2 4 10 33 0 2 3 15 34 0 2 2 20 35 0 2 1 25 36 0 2 0 30 37 0 1 8 0 38 0 1 7 5 39 0 1 6 10 40 0 1 5 15 41 0 1 4 20 42 0 1 3 25 43 0 1 2 30 44 0 1 1 35 45 0 1 1 40 46 0 0 10 0 47 0 0 9 5 48 0 0 8 10 49 0 0 7 15 50 0 0 6 20 2 51 0 0 5 25 52 0 0 4 30 53 0 0 3 35 54 0 0 2 40 55 0 0 1 45 56 0 0 0 50 可见，的确有56种方法。 不过，想用列举的方法解决第二个问题，把一张100元的换成面额较小的都列举出来，可就不怎么方便了，因为方法实在太多。那么，有没有一种办法，能把方法总数算出来呢,有，可以用递推的方法。 要“递推”就要有“递推公式”，要找到“递推公式”就要有适当的符号。 我们用A、B、C、D、E分别表示1元、5元、10元、20元、50元纸币。用A、B、C、D、En分别表示把n元纸币换成这种纸币和比它面额小的纸币一nnnn 共有多少种方法。 为了熟悉这些符号，不妨把前面提到过的那些已知结果和问题，用这些符号表示一下: A,1，表示1张5元的换成1元的，有1种方法。 5 B,3，表示1张10元的换成5元、1元的，有3种方法。 10 C,8，表示1张20元的换成10元、5元、1元的，有8种方法。 20 D,,表示把1张50元的换成20元、10元、5元、1元的，即面额较小的50 有多少种方法, E,,表示把1张100元的换成50元、20元、10元、5元、1元的，即面100 额较小的有多少种方法, 要找到“递推公式”，先从Bn入手。比如B10，表示把1张10的换成5元的和1元的方法总数。这个总数里面包括两种情况，一种是全都是1元的方法总数，即A;另一种是至少有1张5元的方法总数，那就要从10元里先减10 去5元，即B，所以，B,A，B。推而广之，就得到递推公式:B,A10,510510,5nn，B，同理，C,B，C，D,C，D，E,D，E。 n,5nnn,10nnn,20nnn,50 此外还要补充说明三点: 1、因为无论多少钱，换成1元的方法都只有1种，所以当下标n为正整数时，A,1。 n 3 2、当下标n为0时，规定A,1、B,1、C,1、D,1、E,1。 00000 3、当下标n为负数时，规定A负数,0、B,0、C,0、D,0、E负数负数负数,0。 负数 现在，我们就可以用“递推法”解决前面的问题了。 为了熟悉一下这种方法，先把上面用列举法解决过的问题:把一张50元的换成面额较小的方法有多少种,即求D50,,再做一遍。 第一步:根据B,A，B，B,A，B,A，A，B,A，A，A，Bnnn,550504550454050454035,A，A，A，„，A，A，B，可见A的下标从50每次递减5，一直减到等5045401050 于5，说明从A5有50?5,10项，而An恒等于1，B,1，所以B50,100到A5共0 ，1,11。 第二步:根据C,B，C，C,B，C,B，B，C,B，B，B，Cnnn,1050504050403050403020,B，B，B，B，C,B，B，B，B，B，C，其中B50,11，从上一步504030201050403020100 B式可以想到，B40比B、A45两项，即少2，所以B40,11,2,9;50的表达50会少A50 同理，B,9,2,7，B,7,2,5，B,5,2,3;而C,1，所以C50,11，3020100 9，7，5，3，1,36。 第三步:根据D,C，D，D,C，D,C，C，D,C，C，C，Dnnn,20505030503010503010,，其中C50,36，与上一步的C50相比，C30少了B、B40两项，C10又少了1050 B、B20两项，所以C30,36,(11，9),16，C,16,(7，5),4，而D,0，3010,10于是D50,36，16，4，0,56，与“列举法”得到的结果相同。 现在用“递推法”解决第二个问题:把一张100元的换成面额较小的方法有多少种,即求E10,, 0 第一步:B,A，A，A，„，A，A，B,100?5，1,21。 10010095901050 第二步:C,B，B，B，„，B，B，C，其中B10,21，B90比B1001009080201000100A、A95两项，即少2，所以B90,21,2,19;同理，B,19,2,17，B少了1008070,17,2,15，„，B,7,2,5，B,5,2,3;而C,1，于是C10,21，19201000，17，15，13，11，9，7，5，3，1,121。 第三步:D,C，C，C，C，C，D，其中C10,121，从上一步C1001008060402000100的达式可以想到，C80会比C100少前面两项，所以C80,121,(21，19),81;表 同理，C,81,(17，15),49，C,49,(13，11),25，C,25,(9，7),9;604020 而D,1，于是D10,121，81，49，25，9，1,286。 00 4 第四步:E,D，E，其中D10,286，为了求E5，D,C，C，1001005000先求D50505030C，D，从第二步C达式可以想到，C50会比C100少前面5项，所以C5010,10100的表 ,121,(21，19，17，15，13),36;同理，C30比C，C10比C，所50少2项30少2项以C30,36,(11，9),16，C,16,(7，5),4;而D,0，于是D50,36，10,10 16，4，0,56。E,D，E，其中D50,56，E,1，所以E50,56，1,57。最505000 后，E,D，E,286，57,343。即，把一张100元的换成面额较小的方法10010050 有343种。 上面，把1张50元纸币换成1元、5元、10元、20元纸币，究竟有多少种情况的问题，用的是“列举法”。把1张100元纸币换成1元、5元、10元、20元、50元纸币，究竟有多少种情况的问题，用的是“递推法”。这两种方法各有所长各有所短。列举法的优‎‎点是比较具体，缺点是太烦琐。递推法的优点是比较简捷，缺点是太抽象。 除了上面所说的两种方法之外，还有一种方法，就是根据计数的基本原理，采取分类与分步相结合的方法。这种方法既比较具体又不太烦琐，既比较简捷又不太抽象，堪称两全其美。 我们知道，“分类计数”就是先把计数对象分成若干类，一类一类计数，再把各类的计数结果加起来;“分步计数”就是先把计数过程分成若干步，一步一步计数，再把各步的计数结果乘起来。 综合使用这两种方法时，为了使计数既比较具体简捷，又不太烦琐抽象，分类就不能分得过细，分步就不能分得过多。仍然以上面提到的第二个问题为例: 把1张100元纸币换成1元、5元、10元、20元、50元纸币，究竟有多少种情况, 可以把计数对象分成11类，每一类的计数过程最多两步: 第一类:一步到位。把100元全部换成1元或5元的，5元的张数可以从0到20，共21种。 第二类:第一步，把90元换成1元或5元的，5元的张数可以从0到18，共19种;第二步，其余10元，只有换1张10元这1种。总共19×1,19种。 第三类:第一步，把80元换成1元或5元的，5元的张数可以从0到16，共17种;第二步，其余20元，有换2张10元、1张20元，共2种。总共17 5 ×2,34种。 第四类:第一步，把70元换成1元或5元的，5元的张数可以从0到14，共15种;第二步，其余30元，有换3张10元、1张10元1张20元，共2种。总共15×2,30种。 第五类:第一步，把60元换成1元或5元的，5元的张数可以从0到12，共13种;第二步，其余40元，有换4张10元、2张10元1张20元、2张20元，共3种。总共13×3,39种。 第六类:第一步，把50元换成1元或5元的，5元的张数可以从0到10，共11种;第二步，其余50元，有换5张10元、3张10元1张20元、1张10元和2张20元、1张50元，共4种。总共11×4,44种。 第七类:第一步，把40元换成1元或5元的，5元的张数可以从0到8，共9种;第二步，其余60元，有换6张10元、4张10元1张20元、2张10元2张20元、3张20元、1张50元1张10元，共5种。总共9×5,45种。 第八类:第一步，把30元换成1元或5元的，5元的张数可以从0到6，共7种;第二步，其余70元，有换7张10元、5张10元1张20元、3张10元2张20元、1张10元3张20元、1张50元2张10元、1张50元1张20元，共6种。总共7×6,42种。 第九类:第一步，把20元换成1元或5元的，5元的张数可以从0到4，共5种;第二步，其余80元，有换8张10元、6张10元1张20元、4张10元2张20元、2张10元3张20元、4张20元、1张50元3张10元、1张50元和1张20元，共7种。总共5×7,35种。 第十类:第一步，把10元换成1元或5元的，5元的张数可以从0到2，共3种;第二步，其余90元，有换9张10元、7张10元1张20元、5张10元2张20元、3张10元3张20元、1张10元4张20元、1张50元4张10元、1张50元2张20元、1张50元1张20元2张10元，共8种。总共3×8,24种。 第十一类:一步到位。完全没有1元和5元的，有10张10元、8张10元和1张20元、6张10元2张20元、4张10元3张20元、2张10元4张20元、5张20元、2张50元、1张50元2张20元1张10元、1张50元1张20元3张10元、1张50元5张10元，共10种。 6 最后，把各类计数结果加起来，答案是21，19，34，30，39，44，45，42，35，24，10,343(种)。 看来，这种方法的确比较好。有兴趣的网友，不妨用这种方法解决一下第一个问题: 把1张50元纸币换成1元、5元、10元、20元纸币，究竟有多少种情况, 看看是不是56种。 解决“换零钱”的问题，看看“换”的方法究竟有多少种，不是目的，也没有多大实际意义。通过解决这个有一定难度的问题，从中体会运用数学方法的灵活性，感受解决比较复杂的问题所带来的愉悦，证明自己的能力，才是最可贵的。 想不到一个生活中经常遇到的简单问题“换零钱”，其实并不简单，竟然会引出如此精妙的数学思考。这不仅再一次印证了生活中数学无处不在，同时也使我们更进一步体会到数学思想方法的丰富多彩。爱数学、学数学、用数学，永远是人们一种不可替代的智力追求和精神享受。 7