六蚊問題

【上期提要】講開天星碼頭的自動代幣售賣機，就想起多年前的其中一份有關自動售賣機的功課，說起來的確有點無聊，功能是能夠以最少的輔幣進行找贖，假如可使用的輔幣包括 50¢ 、 $1 、 $2 與 $5 ，找 $5.5 的組合必須是 1 個 $5 與 1 個 50¢ 。程式本身並不難寫，只需先扣除最大的輔幣，例如 $5.5 - $5 = 50¢ ，再從大至細考慮哪個輔幣適合找贖，到最後剩係 50¢ ，所以機器找 1 個 $5 與 1 個 50¢。另外，自動售賣機亦要考慮到機內是否備有足夠的輔幣進行交易。用家放入的輔幣亦可作為找贖用途，而當年的問題是：假如機內沒有 $1 ，只有 $2 與 $5 ，要找 $6 的時候，是否應該找 3 個 $2 ？理論上當然可以，但一般的程式只會當作沒有找贖，要編寫一個特別程序才可應付這個特別問題。