## 【31】Coin sums硬幣的總和 英國的貨幣單位有英磅(£)和便士(p),流通的貨幣面值有如下八種: 1p, 2p, 5p, 10p, 20p, 50p, £1 (100p), £2 (200p) 可以這麼來湊夠兩英磅(£2): 1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p 請問總共能用多少種方式來湊夠兩英磅呢? ### 分析:2英磅(£)=200便士(p)就假設: ### a個1英磅(100便士)、b個50便士、c個20便士、d個10便士、e個5便士、f個2便士、g個1便士,2英磅不用算,最後總數再加1即可。 ### 求ax100+bx50+cx20+dx10+ex5+fx2+gx1=200非負整數解幾種? 其中 a=0、1、2 b=0、1、2、3、4 …… f=0~100 100a+50b+20c+10d+5e+2f<=200壘加後,不足200的就是g 用多重迴圈處理即可: ![](https://i.imgur.com/i5ZM555.png) ## 請找總共有多少種方式來湊夠兩英磅呢?