对一个问题的突破！

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