趣味数学028：换零钱问题.doc

换零钱问题换零钱这样的事，在日常生活中经常会遇到。以整元纸币为例，有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元纸币换成这种纸币和比它面额小的纸币一共有多少种方法。为了熟悉这些符号，不妨把前面提到过的那些已知结果和问题，用这些符号表示一下：A51，表示1张5元的换成1元的，有1种方法。B103，表示1张10元的换成5元、1元的，有3种方法。C208，表示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元，即B105，所以，B10A5B105。推而广之，就得到递推公式：BnAnBn5，同理，CnBnCn10，DnCnDn20，EnDnEn50。此外还要补充说明三点：1、因为无论多少钱，换成1元的方法都只有1种，所以当下标n为正整数时，An1。2、当下标n为0时，规定A01、B01、C01、D01、E01。3、当下标n为负数时，规定A负数0、B负数0、C负数0、D负数0、E负数0。现在，我们就可以用“递推法”解决前面的问题了。为了熟悉一下这种方法，先把上面用列举法解决过的问题：把一张50元的换成面额较小的方法有多少种？即求D50？再做一遍。第一步：根据BnAnBn5，B50A50B45A50A45B40A50A45A40B35A50A45A40A10A5B0，可见A的下标从50每次递减5，一直减到等于5，说明从A50到A5共有50510项，而An恒等于1，B01，所以B5010111。第二步：根据CnBnCn10，C50B50C40B50B40C30B50B40B30C20B50B40B30B20C10B50B40B30B20B10C0，其中B5011，从上一步B50的表达式可以想到，B40比B50会少A50、A45两项，即少2，所以B401129；同理，B30927，B20725，B10523；而C01，所以C50119753136。第三步：根据DnCnDn20，D50C50D30C50C30D10C50C30C10D10，其中C5036，与上一步的C50相比，C30少了B50、B40两项，C10又少了B30、B20两项，所以C3036(119)16，C1016(75)4，而D100，于是D5036164056，与“列举法”得到的结果相同。现在用“递推法”解决第二个问题：把一张100元的换成面额较小的方法有多少种？即求E100？第一步：B100A100A95A90A10A5B01005121。第二步：C100B100B90B80B20B10C0，其中B10021，B90比B100少了A100、A95两项，即少2，所以B9021219；同理，B8019217，B7017215，B20725，B10523；而C01，于是C10021191715131197531121。第三步：D100C100C80C60C40C20D0，其中C100121，从上一步C100的表达式可以想到，C80会比C100少前面两项，所以C80121(2119)81；同理，C6081(1715)49，C4049(1311)25，C2025(97)9；而D01，于是D10012181492591286。第四步：E100D100E50，其中D100286，为了求E50先求D50，D50C50C30C10D10，从第二步C100的表达式可以想到，C50会比C100少前面5项，所以C50121(2119171513)36；同理，C30比C50少2项，C10比C30少2项，所以C3036(119)16，C1016(75)4；而D100，于是D5036164056。E50D50E0，其中D5056，E01，所以E5056157。最后，E100D100E5028657343。即，把一张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种。总共19119种。第三类：第一步，把80元换成1元或5元的，5元的张数可以从0到16，共17种；第二步，其余20元，有换2张10元、1张20元，共2种。总共17234种。第四类：第一步，把70元换成1元或5元的，5元的张数可以从0到14，共15种；第二步，其余30元，有换3张10元、1张10元1张20元，共2种。总共15230种。第五类：第一步，把60元换成1元或5元的，5元的张数可以从0到12，共13种；第二步，其余40元，有换4张10元、2张10元1张20元、2张20元，共3种。总共13339种。第六类：第一步，把50元换成1元或5元的，5元的张数可以从0到10，共11种；第二步，其余50元，有换5张10元、3张10元1张20元、1张10元和2张20元、1张50元，共4种。总共11444种。第七类：第一步，把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种。总共9545种。第八类：第一步，把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种。总共7642种。第九类：第一步，把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种。总共5735种。第十类：第一步，把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种。总共3824种。第十一类：一步到位。完全没有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种。最后，把各类计数结果加起来，答案是2119343039444542352410343(种)。看来，这种方法的确比较好。有兴趣的网友，不妨用这种方法解决一下第一个问题：把1张50元纸币换成1元、5元、10元、20元纸