人民幣找零
常說的找零即：用比該幣幣值小的幣種來等額替換。
人民幣找零：即用比該幣幣值小的幣種來等額替換有多少種替換方法。
人民幣的幣種構(gòu)成：100元、50元、20元、10元、5元、2元、1元、5角、2角、1角、5 分、2分、1分共13種面額貨幣。
數(shù)學(xué)模型：層層遞推窮舉法；以上一層窮舉遞推為條件設(shè)置下一層的遞推條件，以控制刪除無效的遞推窮舉。
計(jì)算工具：
聯(lián)想臺式機(jī)Lenovo 510。處理器Intel(R) Core(TM) i5-9400F CPU @ 2.90GHz；
內(nèi)存：8G（機(jī)帶），
Windos 10專業(yè)版，64位操作系統(tǒng), 基于 x64 的處理器
編程軟件：Microsoft ?Visual ?FoxPro 9.0。
編程思路：
方法1：
對直接采用循環(huán)嵌套命令，對循環(huán)條件上限給以有效約束，刪除無效循環(huán)，逐一列舉累計(jì)。因差額部份由壹分來補(bǔ)，壹分一級的循環(huán)取消。
這種方法簡單、簡練、直觀，幣值較小時(shí)很適用。因簡單，巡環(huán)嵌套層級沒有問題（用FOR-ENDF巡環(huán)命令，其嵌套層級可達(dá)13層）。但對幣值較大時(shí)耗時(shí)很長。
只使用了一個(gè)匯總數(shù)據(jù)庫。
方法2：
1、采用分級計(jì)算；對2角以上的各種類型分別窮舉，差額部份由2角及分來湊。因其差額部分分別為：0、1×50分、2×50分、……2000×50分，因此要計(jì)算出用2角及分來找零以上幣值的方法數(shù)。
2、對2角以上的采用窮舉，并將每一種情況及差額逐一裝入數(shù)據(jù)庫。再對應(yīng)將差額部份用2角及分找零的方法數(shù)對應(yīng)調(diào)入到方法數(shù)列中。再對該數(shù)據(jù)庫中的方法數(shù)一列數(shù)字統(tǒng)計(jì)匯總就是該幣值對應(yīng)的找零方法總數(shù)。
3、因巡環(huán)上限是采用逐級迭代控制，算到最后兩分這一級時(shí)就不需再巡環(huán)了，可用一個(gè)數(shù)學(xué)計(jì)算式準(zhǔn)確計(jì)算。使巡環(huán)少嵌套一層
4、計(jì)算出來的數(shù)據(jù)再逐一回代計(jì)算出總數(shù)。
5、使用了一個(gè)匯總數(shù)據(jù)庫，分解到2角這一級時(shí)包含余額的數(shù)據(jù)庫，用2角表現(xiàn)余額種類的數(shù)據(jù)庫。
6、為什么分級分到2角這一級。這是因?yàn)?3種幣值中有12種要參與遞推窮舉中，而巡環(huán)量大的是下面，上面的巡環(huán)量反而小。按一般最優(yōu)考慮選到5角、2角、1角這三級。選到5角，后面的計(jì)算量仍然很大，時(shí)間很長。選到1角這一級，當(dāng)計(jì)算100元找零時(shí)，第一級計(jì)算時(shí)要裝入數(shù)據(jù)庫中的記錄遠(yuǎn)超數(shù)據(jù)庫的上限1700～1800萬條。
方法3：
1、對第二種方法再行優(yōu)化。第二種方法在計(jì)算第二級時(shí)仍用時(shí)較多，因此考慮為采用三級分解計(jì)算：第一級、分解到一元一級，元以后的余額由角、分來窮舉。分解到元一級時(shí)直接調(diào)用后面的數(shù)據(jù)，進(jìn)行計(jì)算匯總到匯總數(shù)據(jù)庫。
2、分解到一元一級后，余額的表現(xiàn)形式最多有（10000/100+1）種（0是一種特殊情況），第二級再將元以后的余額數(shù)分解到一角一級，一角以后的余額由分來窮舉。
3、分解到一角一級后，余額的表現(xiàn)形式最多有（10000/10+1）種（0是一種特殊情況），即分解到一角這一級時(shí)，無論有多少數(shù)據(jù)，其余額必然是上面的一種。再計(jì)算其用分來找零的方法數(shù)就較快了，因這一級的巡環(huán)只有一層。
4、計(jì)算出來的數(shù)據(jù)再逐一回代計(jì)算出總數(shù)。
5、使用了一個(gè)匯總數(shù)據(jù)庫，用1元表現(xiàn)余額種類的數(shù)據(jù)庫，用1角來表現(xiàn)余額種類的數(shù)據(jù)庫。裝入數(shù)據(jù)庫中的記錄最高時(shí)只有（10000/10+1）條，與第二種方法相比小得可以忽略了。
方法2較方法1來說，思路復(fù)雜、編程也要繁雜些。但效率上卻要高得多。
方法3與方法2比較，思路上更復(fù)雜一些，編程也要復(fù)雜。但效率明顯也要高很多。
方法2的算法關(guān)鍵是分級，采用分級雖然使程序變復(fù)雜，但算法上明顯優(yōu)于方法1，一是減少的巡環(huán)嵌套層級、也就減少了對系統(tǒng)的高要求；二是分級使復(fù)雜的巡環(huán)嵌套降低為簡單的巡環(huán)嵌套，提高了效率；三是分級使對數(shù)據(jù)庫容量的要求大為降低。
方法3采用了三次分級與迭代，巡環(huán)嵌套層級進(jìn)一步降低，數(shù)據(jù)庫的數(shù)據(jù)量也很少，進(jìn)步降低了對系統(tǒng)資源的占用。其運(yùn)算時(shí)是先計(jì)算分解到1 角一級余額種類的找零方法數(shù)，其次計(jì)算分解到1元一級時(shí)余額種類的找零方法數(shù)（直接調(diào)用角一級的數(shù)據(jù)），最后計(jì)算分解到元一級時(shí)直接調(diào)用元一級余額種類的數(shù)據(jù)出結(jié)果。當(dāng)然，思路復(fù)雜、編程復(fù)雜了，對編程人員的要求高有所加強(qiáng)。
方法2與方法3的巡環(huán)層級是前后串聯(lián)關(guān)系，不是包含嵌套，所以雖然巡環(huán)有九個(gè)，但真正形成嵌套的級數(shù)卻減少了。
