有一题关于兑换货币的问题————“某人要把手中的一元人民币兑换成零币(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("\nThe 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("\nThe 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
Word教程网 | Excel教程网 | Dreamweaver教程网 | Fireworks教程网 | PPT教程网 | FLASH教程网 | PS教程网 |
HTML教程网 | DIV CSS教程网 | FLASH AS教程网 | ACCESS教程网 | SQL SERVER教程网 | C语言教程网 | JAVASCRIPT教程网 |
ASP教程网 | ASP.NET教程网 | CorelDraw教程网 |