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

换零钱问题换零钱这样的事,在日常生活中经常会遇到以整元纸币为例，有1元、5元、10元、20元、5０元、１00元６种,换零钱就是把面额大的换成面额小的也许你已经换过无数次，不过,你可曾想过换零钱的方法究竟有多少种吗？也许没有想过，其实，这里面的学问大着呢今天我们就来研究研究这个司空见惯的问题.对于面额比较小的,很容易把所有的方法一一列举出来，比如：把一张5元的换成面额较小的,只有5张１元的1种方法;把一张10元的换成面额较小的，有２张５元的、1张５元的5张1元的、10张1元的,3种方法;把一张20元的换成面额较小的，有2张10元的、１张10元的2张5元的、1张１0元的１张５元的５张１元的、4张5元的、3张5元的５张1元的、2张5元的10张1元的、1张5元的1５张1元的、20张1元的，8种方法.那么，把一张50元的换成面额较小的有多少种方法？把一张100元的换成面额较小的有多少种方法？虽然你会想到答案肯定比８种更多,但是你一定想不到，答案竟然会分别达到56种和34３种.不信请往下看:先看第一个问题:把一张50元的换成面额较小的有多少种方法?为了便于有序思考,避免发生重复或遗漏，仍然采用列举的方法. 　 方法序号　20元 10元　5元 1元　　 （单位：张) 　 　 １ 　 　２ 1 ０　　 　　0 　　　 2 　　 2 　　 　 0 2 0 　 　　 3 　 　 2　 　0 　 1　 5　 　4 　2　 0 　 0 　 　10 　5　 　 　 １　　 3 　 0 　 0　 　 　 6 　　 　１ 　 　 2 　 ２ 　　０ 　 　 7 　　　 1 2　 　 1　 　5 　 　　 ８　 1　 ２　 　 0 　１0 　 ９ １ 　 1　 　　 ４ 　　 0 　 　 10 　 1　 　 　1 　 3　 5 　 11 　 1 1 　 ２ 　 10　 　 12　　 1　 １ １ 　1５ 　 　　 １3 　 　 　１ 　 １ 　 　0 　　２0 　 14 １ 　 0 6 0　　 15 1 　 　　０ 　5 5 　 　16 　 1 　　 ０ 　 4 　 1０ 　 １７ 1　 　 　0 　　 ３ 　 １5 　　　　 １8 　 １　 　 0 　 2 20 　 1９ 　 1　　 　 0 　 1 　　 ２5 　 　 　２0　 　 　　1 　 0 　 0 　30　 　　 ２１ 0 　 ５　　　　 0 　 ０ 　 　 ２2 　 0 　 　4　　 　 ２　 　 　0　　 　 23 　 　0 　　4　　 1　　 　　5 　　 24 　　　 　０ 4 ０ 　　 １０　　　 　 25　　 　 　0　 　　 3 　 　4 　 　０ 　 　 　 26 　 0 　 ３　 ３ 5 　 　 2７ 0 　 　3 ２ 　１0 　 　 ２８ 　　0 　 ３　 　 1 15 29 　 　 　0 　 ３ 　 0 　20 　 30 　　0 　 2 　6 0 　 　 31 　 0 　 ２　　 　 ５ 　　 5 　 　 32 0　 　 　2 ４ 　1０ 　 　　 3３ 　　 ０ ２ 　 　3 15　　 　 3４ 0 　　 ２　 2 20 　　 35 　０ 　 2 　 　1 25 　 36 　0 　 2 0　 　 30 　 ３7 　 　 0 　 　 　１ 　 ８ 　 0 　 38　 ０ 　 　１ 　　 7 　 　５　 　 　　39 　　　 0 1 6 　 1０ 　 　 　 40 　 0 　 　1 　 ５ １5 　　 　 ４1　 　 ０ 　 1 　 4 　 2０ 　　 　42 　 0 　 １ 　 3 ２5　　 　　 ４３ 　　 　 0 1 2 　 ３0 　　 　 ４４　 　 　0 1 1 35 　 ４５ 0 　　　 1 　 1 40　 　 46 　 0　　 　0　 　１0 0 　 　 ４７ 　 0　 　　 0　 　 9 　 　５　 　 　48 　 　　　0　 0 　 　８　　　　1０ 　　 49　　 　 0 　 0　 ７ 　 １5 　　 　 50 　 　0　 ０　 　　６　 　２0 　 ５1 　 ０　　 　 0 　　 5　 25 　 　　52 　　 ０ 0 　 4 30 　 5３　 　０ 0 3 　 3５ 　 　　5４ 　 0 0 　 2 　４０　 　　　5５　 　 　0 　 ０　 1 　４5 　　 　 ５6 　　　0 0 　 　０ 　　 50可见，的确有56种方法。

不过,想用列举的方法解决第二个问题，把一张１00元的换成面额较小的都列举出来，可就不怎么方便了,因为方法实在太多那么，有没有一种办法,能把方法总数算出来呢？有,可以用递推的方法要“递推”就要有“递推公式",要找到“递推公式”就要有适当的符号.我们用A、Ｂ、C、D、E分别表示1元、5元、10元、20元、50元纸币用Ａn、Bｎ、Cn、Ｄn、En分别表示把ｎ元纸币换成这种纸币和比它面额小的纸币一共有多少种方法为了熟悉这些符号，不妨把前面提到过的那些已知结果和问题,用这些符号表示一下：A5＝１，表示１张5元的换成１元的，有1种方法.B10＝3，表示1张1０元的换成5元、１元的，有3种方法C20＝8,表示1张20元的换成10元、５元、1元的，有8种方法Ｄ50＝?表示把1张50元的换成20元、1０元、5元、1元的,即面额较小的有多少种方法？Ｅ100=？表示把１张10０元的换成50元、20元、10元、5元、１元的，即面额较小的有多少种方法？要找到“递推公式”，先从Ｂn入手.比如B１０，表示把1张10的换成5元的和1元的方法总数这个总数里面包括两种情况，一种是全都是1元的方法总数,即A１０；另一种是至少有1张５元的方法总数，那就要从10元里先减去５元,即Ｂ10－５，所以,B10=A5+B１0－5。

推而广之，就得到递推公式：Bn=An+Ｂｎ—5，同理，Ｃn=Ｂn＋Cn－１0，Ｄn=Cn＋Dｎ—20,Ｅn＝Dｎ+En－5０此外还要补充说明三点：1、因为无论多少钱，换成１元的方法都只有1种，所以当下标n为正整数时，Aｎ=1.2、当下标ｎ为0时，规定Ａ０＝1、Ｂ0=１、C0=１、D0=１、E０＝13、当下标ｎ为负数时,规定A负数=0、B负数=０、Ｃ负数=0、Ｄ负数＝0、Ｅ负数＝0现在，我们就可以用“递推法”解决前面的问题了为了熟悉一下这种方法,先把上面用列举法解决过的问题：把一张50元的换成面额较小的方法有多少种？即求D５0＝?再做一遍第一步：根据Bn=Aｎ+Ｂn—5,B５0＝Ａ50+B45＝A5０＋A４5＋B40＝A５0＋A45+Ａ40+B35=A50+A45＋A40＋…+A1０＋A5＋B0,可见A的下标从50每次递减５，一直减到等于5，说明从A5０到Ａ5共有50÷5=10项，而Ａｎ恒等于1，B0=1,所以Ｂ50＝１０＋１=11第二步:根据Cn＝Ｂn+Cn－10，C5０＝B5０＋Ｃ40＝B50＋B4０＋Ｃ30=Ｂ50+Ｂ４０+B３０+Ｃ２0=B5０＋Ｂ４0+B３0＋B２0＋C10＝B50＋B４０＋B30＋Ｂ20＋Ｂ10+C0，其中B5０=11,从上一步Ｂ50的表达式可以想到，B40比B50会少Ａ50、A4５两项,即少2,所以B40=11－２=9；同理,B30=9—2=７，B２０＝7－２＝5，B10=５－２＝3;而C０=1，所以C50＝1１＋9+7＋5＋3＋１=3６.第三步：根据Dｎ=Cn＋Dｎ－20,D50=C50+D3０=C５0＋C30+D10＝C5０+C30+C1０＋D—1０,其中C５０=３6，与上一步的Ｃ50相比，Ｃ3０少了B50、B40两项，C10又少了B30、B20两项,所以Ｃ３0=36—（11＋９)=1６，Ｃ１０＝1６－（7＋5)=4，而D－1０＝0，于是D5０＝36+１6+4＋0＝5６，与“列举法”得到的结果相同。

现在用“递推法”解决第二个问题：把一张１０0元的换成面额较小的方法有多少种？即求E10０＝？第一步：Ｂ1０0=A1０0+Ａ95＋A90＋…+Ａ10+A5+Ｂ０=100÷5+1=21.第二步：C1０0＝B100＋Ｂ90＋B８0+…＋Ｂ20+B1０＋C０，其中B1０0＝2１,B９０比B10０少了A100、A95两项，即少2,所以B90=21—2＝19；同理，B80＝１9－2=1７,Ｂ７０＝１7-2=15,…，B20＝7－2=5,B1０=5-2=3；而C０=1,于是Ｃ1０0＝2１+１9+17＋１5+13＋1１+9+７+5＋3+1＝1２１第三步:D１00＝C100+C80+C60+C40+C20＋D0，其中C100＝121，从上一步C１00的表达式可以想到,C8０会比C１０0少前面两项，所以C80＝1２1－(21+19）＝81;同理，Ｃ6０＝81—(17＋１５）＝49，Ｃ４0=49-(13＋11)＝25,Ｃ20=２5－（9＋７)=9；而D0＝1，于是Ｄ100＝121＋８1+49＋2５＋9＋1=286第四步:E10０＝D100+E5０，其中D１00＝２8６，为了求Ｅ５0先求D5０,Ｄ50=C50+C３0+C1０+D－10，从第二步C1０0的表达式可以想到，C５0会比Ｃ１00少前面5项，所以Ｃ50＝121－（21＋19＋1７+１5+13)=36；同理，Ｃ3０比Ｃ50少2项,Ｃ１０比Ｃ３0少２项，所以Ｃ3０=３6—（1１＋9)=１6，C10＝1６－（７+５)＝4；而D－10＝0，于是D5０＝３6+16+4+0＝5６。

E50=D５0＋Ｅ０，其中D50＝５6,E0=1，所以E50＝5６+1＝57.最后，E100=D100+E5０=286＋57＝3４3.即,把一张1０0元的换成面额较小的方法有3４３种上面,把1张５0元纸币换成1元、5元、1０元、２０元纸币，究竟有多少种情况的问题,用的。