WEB开发网
开发学院软件开发C++ 对一个问题的突破! 阅读

对一个问题的突破!

 2008-03-08 12:25:31 来源:WEB开发网   
核心提示: 当你继续不懈的努力时 关于兑换货币问题有一题关于兑换货币的问题————“某人要把手中的一元人民币兑换成零币(5角,2角,1角,5分,2分,1分),问最多有多少种不同的兑换方法,对一个问题的突破!,”其结果最多有4562种不同的兑换方法,常规思路:(1)A,B,C,D,E,F六个变量分别表示这六种零币的数目,会

                                  当你继续不懈的努力时                       --------  关于兑换货币问题 有一题关于兑换货币的问题————“某人要把手中的一元人民币兑换成零币(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


Tags:一个 问题 突破

编辑录入:爽爽 [复制链接] [打 印]
赞助商链接