肖紅德

XIAO Hongde

河南大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，河南 開(kāi)封 475004

School of Mathematics and Statistics,Henan University,Kaifeng,Henan 475004,China

1 概述

計(jì)算機(jī)作為一種工具，在處理需要大量計(jì)算的場(chǎng)合發(fā)揮著巨大的作用，在解決需要大量計(jì)算的問(wèn)題上，一般涉及兩方面：一方面是需要設(shè)計(jì)相關(guān)的算法盡量降低算法的復(fù)雜度；另一方面在通過(guò)計(jì)算機(jī)語(yǔ)言進(jìn)行實(shí)現(xiàn)的時(shí)候還需要對(duì)算法進(jìn)行優(yōu)化，從而使得在解決問(wèn)題時(shí)盡可能地提高效率。本文通過(guò)結(jié)合埃拉托色尼篩法、迪杰斯特拉算法和圖的廣度優(yōu)先遍歷算法的思想，提出了一種用來(lái)計(jì)算平均錢(qián)幣數(shù)量的快速算法，即最少錢(qián)幣數(shù)量篩法，并通過(guò)計(jì)算給定范圍的三種錢(qián)幣組合計(jì)算其平均錢(qián)幣數(shù)量，與動(dòng)態(tài)規(guī)劃算法相比，計(jì)算速度明顯加快，與貪心算法相比，計(jì)算結(jié)果更好。對(duì)于給定范圍、給定錢(qián)幣種類(lèi)，如何確定錢(qián)幣組合這個(gè)問(wèn)題，本文通過(guò)對(duì)不同錢(qián)幣之間數(shù)值特征的分析，給出了各個(gè)數(shù)值滿足的擬合曲線，從而在尋找最佳錢(qián)幣種類(lèi)組合上使得算法的時(shí)間復(fù)雜度大大降低，程序的運(yùn)算時(shí)間大大縮短。文中選擇MATLAB R2017b作為運(yùn)行環(huán)境，針對(duì)上述提出的兩種算法進(jìn)行了具體實(shí)現(xiàn)。

2 相關(guān)研究

關(guān)于紙幣面值的組合情況研究，Jeffrey已經(jīng)給出了相關(guān)研究結(jié)果，見(jiàn)參考文獻(xiàn)[1]。其結(jié)果如表1所示。

表2給出的貨幣最佳發(fā)行方案是通過(guò)動(dòng)態(tài)規(guī)劃算法計(jì)算出來(lái)的。動(dòng)態(tài)規(guī)劃有關(guān)的算法見(jiàn)參考文獻(xiàn)[2-4]，本文計(jì)算的結(jié)果與Jeffrey給出的結(jié)果不同，原因是Jeffrey計(jì)算的范圍包括1但不包括100，且按照100進(jìn)行平均。如果本文也按照這樣的方法進(jìn)行計(jì)算，則得到的結(jié)果與Jeffrey相同。其他錢(qián)幣方案中平均錢(qián)幣數(shù)量的計(jì)算與此類(lèi)似。

對(duì)于給定某個(gè)值，在計(jì)算其所需要最少數(shù)量錢(qián)幣組合的時(shí)候，如果錢(qián)幣種類(lèi)多于兩種，盡管貪心算法計(jì)算速度比較快，卻一般不能使用貪心算法進(jìn)行計(jì)算，貪心算法的相關(guān)內(nèi)容見(jiàn)參考文獻(xiàn)[2，5-6]。這是由于對(duì)于貪心算法計(jì)算出來(lái)的結(jié)果，在某些組合下不能得到最優(yōu)結(jié)果。比如，使用貪心算法，對(duì)于1-5-16-23-33這種組合，在計(jì)算32最優(yōu)組合方案時(shí)，使用貪心算法計(jì)算的結(jié)果是32=23×1+5×1+1×4，一共需要6個(gè)錢(qián)幣，而如果使用動(dòng)態(tài)規(guī)劃計(jì)算結(jié)果為32=16×2，一共需要2個(gè)錢(qián)幣。因此，貪心算法在有些情況下得到的不是最優(yōu)錢(qián)幣組合。

對(duì)于錢(qián)幣種類(lèi)的確定還有很多其他相關(guān)研究，比如參考文獻(xiàn)[7]研究了有關(guān)增加某個(gè)錢(qián)幣面額的數(shù)值分析和確定方法。

3 確定平均錢(qián)幣數(shù)量的快速計(jì)算方法——最少錢(qián)幣數(shù)量篩法

借助埃拉托色尼篩法（見(jiàn)參考文獻(xiàn)[8-10]）、迪杰斯特拉算法（見(jiàn)參考文獻(xiàn)[11-13]）、圖的廣度優(yōu)先遍歷算法（見(jiàn)參考文獻(xiàn)[11]）的思想，提出一種新的對(duì)于給定錢(qián)幣種類(lèi)之后在一定范圍內(nèi)進(jìn)行快速計(jì)算最少需要錢(qián)幣數(shù)量的算法，以下稱之為最少錢(qián)幣數(shù)量篩法。

最少錢(qián)幣數(shù)量篩法實(shí)現(xiàn)的具體計(jì)算過(guò)程如下：

首先令W為給定數(shù)值的錢(qián)幣組合，V為一定范圍內(nèi)的數(shù)據(jù)集合，cur:=1，cur值用于表示當(dāng)前能夠計(jì)算出來(lái)的錢(qián)幣值所需要的最少錢(qián)幣數(shù)量，把需要計(jì)算的錢(qián)幣范圍V分成兩組：

（1）S，已求出最小錢(qián)幣數(shù)量的錢(qián)幣集合（初始時(shí)為0）；

（2）T:=V-S，尚未確定最小錢(qián)幣數(shù)量的錢(qián)幣集合（初始時(shí)為V的全集）。

然后進(jìn)行以下計(jì)算過(guò)程：

（1）將S中新加入的每一個(gè)數(shù)加上W中的每一個(gè)數(shù)（初始時(shí)認(rèn)為新加入的數(shù)是0），若得到的數(shù)在T中，則將其加入到S中，其錢(qián)幣數(shù)量記為cur；

（2）修改集合T，去除（1）中S新加入數(shù)的集合；

（3）將cur值加1，即cur:=cur+1；

（4）重復(fù)執(zhí)行（1）～（3），直到集合T為空。

4 對(duì)任意數(shù)量范圍內(nèi)通過(guò)構(gòu)造錢(qián)幣組合確定平均錢(qián)幣數(shù)量

對(duì)于不同錢(qián)幣數(shù)量最優(yōu)組合的確定，給定錢(qián)幣范圍[1,n]，N種錢(qián)幣組合的情況，可以構(gòu)造(n0/N,n1/N,…,n(N-1)/N)這種按照等比數(shù)列規(guī)律出現(xiàn)的一組數(shù)字，這里用(1,a,…,aN-1)表示，其中a=n1/N，為了表達(dá)方便，假設(shè)其為整數(shù)。對(duì)于這樣的構(gòu)造方案，其好處是在計(jì)算其平均錢(qián)幣數(shù)量時(shí)可以使用貪心算法來(lái)得到某個(gè)數(shù)值的錢(qián)幣數(shù)量，這樣方便統(tǒng)計(jì)其平均錢(qián)幣數(shù)量。

表1 Jeffrey的貨幣最佳發(fā)行方案

表2 本文計(jì)算出來(lái)的貨幣最佳發(fā)行方案

由上面的構(gòu)造組合可以得出以下結(jié)論：錢(qián)幣組合方案的最佳組合不高于構(gòu)造組合(1,a,…,aN-1)。對(duì)于這樣的構(gòu)造組合，下面通過(guò)計(jì)算得到平均錢(qián)幣數(shù)量。

f(1)=最大錢(qián)幣值為1的錢(qián)幣數(shù)值數(shù)量

f(2)=最大錢(qián)幣值為a的錢(qián)幣數(shù)值數(shù)量

…

f(N)=最大錢(qián)幣值為aN-1的錢(qián)幣數(shù)值數(shù)量

則有：

最后+1表示的是aN，即n這一個(gè)數(shù)的表示。從而有：

從而可以推出總數(shù)量為：

進(jìn)而說(shuō)明上述計(jì)算的錢(qián)幣數(shù)值包含錢(qián)幣范圍內(nèi)的所有錢(qián)幣數(shù)值。

對(duì)于通過(guò)上述方案構(gòu)造的錢(qián)幣組合，可以計(jì)算其平均錢(qián)幣數(shù)量，具體計(jì)算過(guò)程如下：令t()

i=由所有最大錢(qián)幣面額為ai-1的錢(qián)幣組合錢(qián)幣數(shù)量之和，其中1≤i≤N。則有：

最后+a表示的是aN,即n這一個(gè)數(shù)的表示，需要的錢(qián)幣數(shù)量為a。

因此，需要的平均錢(qián)幣數(shù)量為：

對(duì)于三種錢(qián)幣的組合，通過(guò)遍歷計(jì)算得到的平均錢(qián)幣數(shù)量最優(yōu)值和上述構(gòu)造方法得到的平均錢(qián)幣數(shù)量比值大約在（0.95，1.00）之間，并且隨著范圍的增大，比值也趨向于增大。

5 構(gòu)造組合和最優(yōu)組合的對(duì)比

對(duì)于最優(yōu)組合的設(shè)計(jì)，需要將第一個(gè)錢(qián)幣固定為1，其他錢(qián)幣種類(lèi)需要進(jìn)行遍歷得到。對(duì)于錢(qián)幣種類(lèi)為2的錢(qián)幣組合，通過(guò)第4章關(guān)于平均錢(qián)幣數(shù)量的計(jì)算比較容易得到，第二個(gè)錢(qián)幣值是關(guān)于a0.5的向上取整或向下取整的整數(shù)，見(jiàn)表3和圖1。對(duì)于錢(qián)幣種類(lèi)大于2的錢(qián)幣種類(lèi)的確定，需要通過(guò)遍歷方式得到。

表3 兩種錢(qián)幣組合在最優(yōu)錢(qián)幣組合下平均錢(qián)幣數(shù)量表

圖1 兩種錢(qián)幣組合平均數(shù)量理論值與實(shí)際值對(duì)比

圖1說(shuō)明：藍(lán)線表示在最優(yōu)錢(qián)幣組合下的平均錢(qián)幣數(shù)量圖，綠色表示通過(guò)構(gòu)造錢(qián)幣組合得到的平均錢(qián)幣數(shù)量理論值，其公式為y=x1/2-1+x-1/2，其中x表示錢(qián)幣范圍，y表示平均需要的錢(qián)幣數(shù)量。通過(guò)圖1可以發(fā)現(xiàn)，對(duì)于兩種錢(qián)幣的組合，理論值和實(shí)際值基本完全吻合。

以下討論如何確定錢(qián)幣的最優(yōu)組合問(wèn)題。

對(duì)于三種錢(qián)幣的最優(yōu)錢(qián)幣種類(lèi)確定問(wèn)題，當(dāng)取值范圍很大時(shí)，需要遍歷次數(shù)太多，因此需要盡可能縮小遍歷次數(shù)。通過(guò)計(jì)算可知，對(duì)于113≤n≤253的情況，第一個(gè)數(shù)是固定的1，第二個(gè)數(shù)通過(guò)已有例子的模擬（見(jiàn)圖4和圖5）可以確定其曲線擬合表達(dá)式為n1040/2711+1255/452，擬合值與真實(shí)值的差值在區(qū)間[-8197/521,8107/702]上，第三個(gè)數(shù)的曲線擬合表達(dá)式為n25391/38087+1235/478，擬合值與真實(shí)值的差值在區(qū)間[-8197/521,8107/702]上。第二個(gè)數(shù)的平方與第三個(gè)數(shù)的比值處于(2.5,3.2)之間。通過(guò)對(duì)第二個(gè)數(shù)和第三個(gè)數(shù)以及第二個(gè)和第三個(gè)數(shù)之間關(guān)系的限定，可以大大減少遍歷次數(shù)。

曲線擬合的實(shí)現(xiàn)是按照最小二乘法原理進(jìn)行實(shí)現(xiàn)的，有關(guān)曲線擬合的MATLAB實(shí)現(xiàn)和最小二乘法原理見(jiàn)參考文獻(xiàn)[14-18]。

對(duì)于三種錢(qián)幣的最優(yōu)錢(qián)幣組合，最終所得結(jié)果見(jiàn)表4和圖2。

表4 三種錢(qián)幣組合在最優(yōu)錢(qián)幣組合下平均錢(qián)幣數(shù)量表

圖2 三種錢(qián)幣組合平均數(shù)量理論值與實(shí)際值對(duì)比

圖2說(shuō)明：藍(lán)色表示在最優(yōu)錢(qián)幣組合下的平均錢(qián)幣數(shù)量圖，綠色表示通過(guò)構(gòu)造錢(qián)幣組合得到的平均錢(qián)幣數(shù)量圖，其公式為y=3×a/2-3/2+a-2，其中a=n1/3。由圖2可知，構(gòu)造值比真實(shí)值要高，真實(shí)值與構(gòu)造值之比主要集中于0.96～0.97之間。

以下是計(jì)算3個(gè)最優(yōu)錢(qián)幣組合與數(shù)值范圍n相互之間關(guān)系的模擬效果圖。圖3中橫軸表示數(shù)值范圍n，縱軸表示第二個(gè)數(shù)的平方與第三個(gè)數(shù)的比值。第二個(gè)數(shù)和第三個(gè)數(shù)之間差值的計(jì)算可以通過(guò)該結(jié)果進(jìn)行估計(jì)。

第二個(gè)參數(shù)和第三個(gè)參數(shù)之間的關(guān)系可以通過(guò)圖3的模擬結(jié)果進(jìn)行估計(jì)。第二個(gè)數(shù)的數(shù)量級(jí)可以通過(guò)圖4的模擬結(jié)果進(jìn)行估計(jì)。第三個(gè)數(shù)的數(shù)量級(jí)可以通過(guò)圖5的模擬結(jié)果進(jìn)行估計(jì)。

圖3 三種錢(qián)幣組合第二個(gè)數(shù)與第三個(gè)數(shù)的關(guān)系

圖4 三種錢(qián)幣組合第二個(gè)錢(qián)幣值的擬合效果圖

圖3說(shuō)明：在該圖中，最大值為1296/409（約為3.1687），最小值為361/139（約為2.5971）。

圖5 三種錢(qián)幣組合第三個(gè)錢(qián)幣值的擬合效果圖

圖4說(shuō)明：藍(lán)色曲線表示第二個(gè)錢(qián)幣種類(lèi)的真實(shí)值，綠色表示第二個(gè)錢(qián)幣種類(lèi)的曲線擬合值，其擬合曲線方程為y=x1040/2711+1255/452，其中x表示錢(qián)幣的范圍，y表示第二個(gè)錢(qián)幣種類(lèi)的曲線擬合值，擬合值和真實(shí)值的最大差值為1216/985（約為1.2345），最小差值為-853/475（約為-1.7958）。

圖5說(shuō)明：藍(lán)色曲線表示第三個(gè)錢(qián)幣種類(lèi)的真實(shí)值，綠色表示第三個(gè)錢(qián)幣種類(lèi)的曲線擬合值，其擬合曲線方程為y=x25391/38087+1235/478，其中x表示錢(qián)幣的范圍，y表示第三個(gè)錢(qián)幣種類(lèi)的曲線擬合值，擬合值和真實(shí)值的最大差值為8107/702（約為11.5484），最小差值為-8197/521（約為-15.7332）。

四種以及更多種錢(qián)幣組合的確定更為復(fù)雜。與三種錢(qián)幣組合的確定類(lèi)似，第一個(gè)數(shù)是固定的1，后面的數(shù)值需要通過(guò)遍歷或者通過(guò)已經(jīng)找出的數(shù)值發(fā)現(xiàn)數(shù)值規(guī)律，在規(guī)律的基礎(chǔ)上進(jìn)行限制，這里不再討論。

6 結(jié)論

本文提出了一種對(duì)于給定錢(qián)幣組合在給定范圍情況下快速計(jì)算需要的平均錢(qián)幣數(shù)量的方法，對(duì)于三種錢(qián)幣組合，給出了一種確定錢(qián)幣范圍的計(jì)算方法，并在此基礎(chǔ)上對(duì)錢(qián)幣種類(lèi)的范圍進(jìn)行了限制，其好處是可以大大減少對(duì)于最佳錢(qián)幣組合的搜索范圍。