對一個問題的突破！

2019-11-17 05:47:31

字體：大中小

來源：轉載

供稿：網友

                                                               當你繼續不懈的努力時                                           -------- 關于兌換貨幣問題有一題關于兌換貨幣的問題————“某人要把手中的一元人民幣兌換成零幣（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;}  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

上一篇：對五星紅旗的注釋

下一篇：隊列實現打印楊輝三角