当你继续不懈的努力时
-------- 关于兑换货币问题
有一题关于兑换货币的问题————“某人要把手中的一元人民币兑换成零币（5角,2角,1角,5分,2分,1分），问最多有多少种不同的兑换方法。”其结果最多有4562种不同的兑换方法。
常规思路：
（1）A,B,C,D,E,F六个变量分别表示这六种零币的数目。对各个变量初值从0开始，步长为1分别递增到1元，即依次增到2,5,10,20,50,100,若满足50A+20B+10C+5D+2E+F=100.为一种兑换方法，利用一个六重循环嵌套，可得所有的结果，即最多的不同兑换方法数。这是最轻易想到的解法。但是需要3*6*11*21*51*101=21417858次，才有结果！（程序结构如书中，在此略），
（2）若使终值排除大于100的，则可以上百倍的提高效率。分别令A,B,C,D,E,F的终值为2,(100-50A)/20,(100-50A-20B)/10,(100-50A-20B-10C)/5,(100-50A-20B-10C-5D)/2 ,100-50A-20B-10C-5D-2E。则需执行104560次可得出结果。另对F的终值，发现其数据的非凡性，可不必使用到循环，只需嵌套到E变量即可。此时为4562次即可。（程序结构如书中，在此略）
（3）实际上对A，B，C，D的每一组取值，在第五层循环内总共给N（解法数）增加了
[（100-50A-20B-10C-5D）/2]+1次个1。所以只需在第四层循环的循环体内给N直接加上第五层循环的执行次数就可。最终四重循环，只需循环体343次。认为最好的解法。（程序结构如书中，在此略《结构化程序设计教程》，作者宁正元。陕西电子杂志社出版。其作者也就是现在我这门课的任教教授。）
巧解如下:（我的研究）
(1).因为不定方程5*x+2*y+z=m,中的系数的最大公约数为1,也即（5,2,1）=1; 故设最多可以有多少种不同的兑换方法为A(m),且为：F(x)=1/〔1-x〕*〔1-x^2〕*〔1-x^5〕的x^m的系数。且F(x)可表示为：F（x）=
A3/(1-x)^3+A2/(1-x)^2+A1/(1-x)+B1/(1+x)+(C1x+D1)/[x^2+(1-sqrt(5))/2*x+1]+(C2x+D2)/[x^2+(1+sqrt(5))/2*x+1]。即可表示为：F(x)=∑Ami/(ai-x)^mi 的形式。其中Ami为常数，ai为：（1-x）*（1-x^2）*(1-x^5)=0 的根，mi为重根数目。设Ami/(ai-xi)^mi=Ami*ai^(-mi)*(1-x/ai)^(-mi)的x^m的系数为?（m）.由二项式展开定理得：?（m）=Ami*（(ai)^(-(mi+m))）* (m+mi-1) *(m+mi-2)…(m+1)/(mi-1)! 故对本题有:50*A+20*B+10*C+5*D+2*E+F=100令5*A+2*B+C=m,则：5*D+2*E+F=100-10*m即可.有A(m)= ∑? i（m）. 故而有源程序（1）。
（2）从50A+20B+10C+5D+2E+F=100,这些数据可组合为5(10A+D)+2(10B+E)+10C+F=100,又由10x+y=m,m为整数，x,y为非负整数，可知 (x,y)有[m/10]+1对。故有新解法。故而有源程序（2） 此种解法抛开了许多概念，单纯发掘它的数关系。只须541次即可。少为差些。
（3）不过如下更好。朋友们，今天我发现了新解法了；
50a+20b+10c+5d+2e+f=100=> 10(5a+c)+5(4b+d)+2e+f=100
（1），（2）都突破了记录！！值得大家体会啊！！^_^ ^_^
运用数学这门学问,广开思路.尤其对于数字上的编程，
我建议大家多研究数论等方面的著作，我尊敬的老师，华罗庚，陈景润的著作！！
综上体现了解法其实可多想些方面，会有惊人的发现！结果会一鸣惊人之势！！
欢迎大家扩展思路，提出新方法。
(1）源程序为：
/*--turboc2.0 --*/
#define pi 3.1415926
#include<math.h>
int doit(int m)
{
int numb;
double num,t;
t=2*cos((float)(144-72*(m+1))*pi/180)+2*cos((float)(108-144*(m+1))*pi/180);
if(m==0) return 1;
else
if(m%2==0)
num=(double)(m*m+3*m+2)/20+(double)(m+1)/4+0.325+0.125+0.02*t;
else
num=(double)(m*m+3*m+2)/20+(double)(m+1)/4+0.325-0.125+0.02*t; /*即为前面的x^m系数*/
numb=(int) (num+0.5);/*整数即为整数解数目，向上取整！*/
return numb;
}
/*---------main--------------*/
main()
{
int n,number1,number2,number=0;
for(n=0;n<=10;n++)
{
number1=doit(n);
number2=doit(100-10*n);
number=number+number1*number2;
}
printf(" The number of sort is %d.",number);
}
（2）源程序为：
main()
{
int i,j,num=0;
for(i=0;i<=20;i++)
for(j=0;j<=(100-5*i)/2;j++)
num=num+(i/10+1)*(j/10+1)*((100-5*i-2*j)/10+1);
printf(" The total number of sort is %d.",num);
}
（3）源程序为：
sortnum=0;
for(i=0;i<=10;i++)
for(j=0;j<=(100-10i)/5;j++)
sortnum=sortnum+(i/10 + 1)*(j/4 + 1)*((100-10i-5j)/2 + 1)
有什么新的发现与巧解,我所预感到不只这么多解法！
我喜欢多动脑筋的解法.
欢迎交流.
QQ: 370917994
email:iamlovingclanguage@tom.com
|
