趣味数学换零钱问题

《趣味数学换零钱问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、换零钱问题换零钱这样的事，在日常生活中经常会遇到。以整元纸币为例，有1元、5元、10元、20元、50元、100元6种，换零钱就是把面额大的换成面额小的。也许你已经换过无数次，不过，你可曾想过换零钱的方法究竟有多少种吗？也许没有想过，其实，这里面的学问大着呢。今天我们就来研究研究这个司空见惯的问题。对于面额比较小的，很容易把所有的方法一一列举出来，比如：把一张5元的换成面额较小的，只有5张1元的1种方法；把一张10元的换成面额较小的，有2张5元的、1张5元的5张1元的、10张1元的，3种方法；把一张20

2、元的换成面额较小的，有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元的换成面额较小的有多少种方法？为了便于有序思考，避免发生重复或遗漏，仍然采用列举的方法

3、。　　　方法序号　20元　10元　5元　1元(单位：张)121002202032015420010513006122071215812010911401011357/71111210121111513110201410601510551610410171031518102201910125201003021050022042023041524040102503402603352703210280311529030203002603102553202410330231534022203502125360

4、20303701803801753901610400151541014204201325430123044011354501140460010047009548008107/749007155000620510052552004305300335540024055001455600050可见，的确有56种方法。不过，想用列举的方法解决第二个问题，把一张100元的换成面额较小的都列举出来，可就不怎么方便了，因为方法实在太多。那么，有没有一种办法，能把方法总数算出来呢？有，可以用递推的方法。要“递推”就要

5、有“递推公式”，要找到“递推公式”就要有适当的符号。我们用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元

6、、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

7、－20，En＝Dn＋En－50。此外还要补充说明三点：1、因为无论多少钱，换成1元的方法都只有1种，所以当下标7/7n为正整数时，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＝

8、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＋C