全力以赴每一天

• 火車站之自動售票機接受50元、10元、5元、1元的硬幣，試寫出一個程式，算出購買127元之車票時，所需投入幣數最少之組合及其數量(速算法)。

import java.util.Scanner;public class P4_1 {	public static void main(String[] args) {
/* * 金額縮到50元來說明會比較簡單些， 硬幣總類也先縮減到10元、5元、1元三種， 組合方程式為 * 10X+5Y+Z=50，可能的組合會有(x,y,x)： (5,0,0)=5 (4,2,0)=6 (3,4,0)=7 (2,6,0)=8 * (1,8,0)=9 (4,1,5)=10 (0,10,0)=10 (3,3,5)=11 (2,5,5)=12 (1,7,5)=13 (0,9,5)=14 * (3,2,10)=15 (2,4,10)=16 (1,6,10)=17 (0,8,10)=18 (3,1,15)=19 (2,3,15)=20 * (1,5,15)=21 (0,7,15)=22 (3,0,20)=23 (2,2,20)=24 (1,4,20)=25 (0,6,20)=26 * (2,1,25)=28 (1,3,25)=29 (0,5,25)=30 (2,0,30)=32 (1,2,30)=33 (0,4,30)=34 * (1,1,35)=37 (0,3,35)=38 (1,0,40)=41 (0,2,40)=42 (0,1,45)=46 (0,0,50)=50 *  * 從組合可看出一現象，1元硬幣所佔比重愈大時，總幣數增加， * 反之，10元硬幣所佔比重愈大時，總幣數減少， * 所以並不需要每個組合都去驗證，先將幣數分配給最大幣值之硬幣， * 剩餘之數再分配各次大幣值之硬幣，依此類推，即可找出最少幣數之組合。 * 此方法結果和用for迴圈一樣，缺點是無法逐一印出全部符合之組合 */		int coin50n, coin10n, coin5n, coin1n;		coin50n = coin10n = coin5n = coin1n = 0;		Scanner scn = new Scanner(System.in);		System.out.println("請輸入要計算的金額：");		int amount = scn.nextInt();
		// 如果amount大於等於50，將amount除以50後之商指定給coin50n		// 將amount除以50取餘數指定給amount，如57/50=1...7，		// 1指定給coin50n， 代表50元之硬幣數為1個，7指定給amount		if (amount >= 50) {			coin50n = amount / 50;			amount = amount % 50;		}
		// 經重新指定之amount如大於等於10		// 將amount除以10之商指定給coin10n，餘數指定給amount		if (amount >= 10) {			coin10n = amount / 10;			amount = amount % 10;		}
		// 經重新指定之amount如大於等於5		// 將amount除以5之商指定給coin5n，餘數指定給amount		if (amount >= 5) {			coin5n = amount / 5;			amount = amount % 5;		}
		// 剩餘之amount即為1元硬幣之數		coin1n = amount;
		System.out.printf("最小數量組合為：\n50元硬幣%d個\n10元硬幣%d個\n5元硬幣%d個\n1元硬幣%d個\n", coin50n, coin10n, coin5n, coin1n);		System.out.println("硬幣總共" + (coin50n + coin10n + coin5n + coin1n) + "個");		scn.close();	}}

• 輸出結果：

請輸入要計算的金額：127最小數量組合為：50元硬幣2個10元硬幣2個5元硬幣1個1元硬幣2個硬幣總共7個