换零钱问题

换零钱问题 换零钱这样的事，在日常生活中经常会遇到。以整元纸币为例，有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 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 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元纸币。用An、Bn、Cn、Dn、En分别表示把n元纸币换成这种纸币和比它面额小的纸币一共有多少种方法。 为了熟悉这些符号，不妨把前面提到过的那些已知结果和问题，用这些符号表示一下： A5＝1，表示1张5元的换成1元的，有1种方法。 B10＝3，表示1张10元的换成5元、1元的，有3种方法。 C20＝8，表示1张20元的换成10元、5元、1元的，有8种方法。 D50＝？表示把1张50元的换成20元、10元、5元、1元的，即面额较小的有多少种方法？ E100＝？表示把1张100元的换成50元、20元、10元、5元、1元的，即面额较小的有多少种方法？ 要找到“递推公式”，先从Bn入手。比如B10，表示把1张10的换成5元的和1元的方法总数。这个总数里面包括两种情况，一种是全都是1元的方法总数，即A10；另一种是至少有1张5元的方法总数，那就要从10元里先减去5元，即B10－5，所以，B10＝A5＋B10－5。推而广之，就得到递推公式：Bn＝An＋Bn－5，同理，Cn＝Bn＋Cn－10，Dn＝Cn＋Dn－20，En＝Dn＋En－50。 此外还要补充说明三点： 1、因为无论多少钱，换成1元的方法都只有1种，所以当下标n为正整数时，An＝1。 2、当下标n为0时，规定A0＝1、B0＝1、C0＝1、D0＝1、E0＝1。 3、当下标n为负数时，规定A负数＝0、B负数＝0、C负数＝0、D负数＝0、E负数＝0。 现在，我们就可以用“递推法”解决前面的问题了。 为了熟悉一下这种方法，先把上面用列举法解决过的问题：把一张50元的换成面额较小的方法有多少种？即求D50＝？再做一遍。 第一步：根据Bn＝An＋Bn－5，B50＝A50＋B45＝A50＋A45＋B40＝A50＋A45＋A40＋B35＝A50＋A45＋A40＋…＋A10＋A5＋B0，可见A的下标从50每次递减5，一直减到等于5，说明从A50到A5共有50÷5＝10项，而An恒等于1，B0＝1，所以B50＝10＋1＝11。 第二步：根据Cn＝Bn＋Cn－10，C50＝B50＋C40＝B50＋B40＋C30＝B50＋B40＋B30＋C20＝B50＋B40＋B30＋B20＋C10＝B50＋B40＋B30＋B20＋B10＋C0，其中B50＝11，从上一步B50的表达式可以想到，B40比B50会少A50、A45两项，即少2，所以B40＝11－2＝9；同理，B30＝9－2＝7，B20＝7－2＝5，B10＝5－2＝3；而C0＝1，所以C50＝11＋9＋7＋5＋3＋1＝36。 第三步：根据Dn＝Cn＋Dn－20，D50＝C50＋D30＝C50＋C30＋D10＝C50＋C30＋C10＋D－10，其中C50＝36，与上一步的C50相比，C30少了B50、B40两项，C10又少了B30、B20两项，所以C30＝36－(11＋9)＝16，C10＝16－(7＋5)＝4，而D－10＝0，于是D50＝36＋16＋4＋0＝56，与“列举法”得到的结果相同。 现在用“递推法”解决第二个问题：把一张100元的换成面额较小的方法有多少种？即求E100＝？ 第一步：B100＝A100＋A95＋A90＋…＋A10＋A5＋B0＝100÷5＋1＝21。 第二步：C100＝B100＋B90＋B80＋…＋B20＋B10＋C0，其中B100＝21，B90比B100少了A100、A95两项，即少2，所以B90＝21－2＝19；同理，B80＝19－2＝17，B70＝17－2＝15，…，B20＝7－2＝5，B10＝5－2＝3；而C0＝1，于是C100＝21＋19＋17＋15＋13＋11＋9＋7＋5＋3＋1＝121。 第三步：D100＝C100＋C80＋C60＋C40＋C20＋D0，其中C100＝121，从上一步C100的表达式可以想到，C80会比C100少前面两项，所以C80＝121－(21＋19)＝81；同理，C60＝81－(17＋15)＝49，C40＝49－(13＋11)＝25，C20＝25－(9＋7)＝9；而D0＝1，于是D100＝121＋81＋49＋25＋9＋1＝286。 第四步：E100＝D100＋E50，其中D100＝286，为了求E50先求D50，D50＝C50＋C30＋C10＋D－10，从第二步C100的表达式可以想到，C50会比C100少前面5项，所以C50＝121－(21＋19＋17＋15＋13)＝36；同理，C30比C50少2项，C10比C30少2项，所以C30＝36－(11＋9)＝16，C10＝16－(7＋5)＝4；而D－10＝0，于是D50＝36＋16＋4＋0＝56。E50＝D50＋E0，其中D50＝56，E0＝1，所以E50＝56＋1＝57。最后，E100＝D100＋E50＝286＋57＝343。即，把一张100元的换成面额较小的方法有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×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种。 最后，把各类计数结果加起来，答案是21＋19＋34＋30＋39＋44＋45＋42＋35＋24＋10＝343(种)。 看来，这种方法的确比较好。有兴趣的网友，不妨用这种方法解决一下第一个问题： 把1张50元纸币换成1元、5元、10元、20元纸币，究竟有多少种情况？ 看看是不是56种。 解决“换零钱”的问题，看看“换”的方法究竟有多少种，不是目的，也没有多大实际意义。通过解决这个有一定难度的问题，从中体会运用数学方法的灵活性，感受解决比较复杂的问题所带来的愉悦，证明自己的能力，才是最可贵的。 想不到一个生活中经常遇到的简单问题“换零钱”，其实并不简单，竟然会引出如此精妙的数学思考。这不仅再一次印证了生活中数学无处不在，同时也使我们更进一步体会到数学思想方法的丰富多彩。爱数学、学数学、用数学，永远是人们一种不可替代的智力追求和精神享受。