所持金と購入価格から最適なお釣りを算出するプログラム
偶然↓を見つけて面白そうだったのでやってみた。
大学のプログラミング課題ができません。 - 最近大学でjavaを始めたんですが課題... - Yahoo!知恵袋
// 1.所持金の貨幣枚数を計算 // 2.おつり(1の貨幣から算出可能な金額 - 買い物金額)のリストを算出 // 3.2でもとめたすべての金額について、貨幣枚数を計算 // 4.3の貨幣枚数で一番少ないものを求める import java.util.*; public class Kadai { private static int[] kahei_arr = {1000, 500, 100, 50, 10, 5, 1}; // 入力:金額、出力:最小貨幣枚数map<貨幣(ex:500)、枚数> private static Map<Integer, Integer> getKaheiMaisuMap(int kingaku) { Map<Integer, Integer> map = new TreeMap<Integer, Integer>(); for (int kahei : kahei_arr) { int maisu = kingaku / kahei; kingaku = kingaku % kahei; map.put(kahei, maisu); } return map; } // 入力:貨幣枚数map<貨幣(ex:500)、枚数>、出力：算出可能な金額のリスト private static List<Integer> getKingakuList(Map<Integer, Integer> kahei_maisu_map) { List<Integer> list = new ArrayList<Integer>(); for (int i=0; i <= kahei_maisu_map.get(1000) * 1000; i += 1000) { for (int j=0; j <= kahei_maisu_map.get(500) * 500; j += 500) { for (int k=0; k <= kahei_maisu_map.get(100) * 100; k += 100) { for (int l=0; l <= kahei_maisu_map.get(50) * 50; l += 50) { for (int m=0; m <= kahei_maisu_map.get(10) * 10; m += 10) { for (int n=0; n <= kahei_maisu_map.get(5) * 5; n += 5) { for (int o=0; o <= kahei_maisu_map.get(1) * 1; o += 1) { list.add(i+j+k+l+m+n+o); } } } } } } } return list; } public static void main(String[] args) { Scanner stdIn = new Scanner(System.in); System.out.print("所持金は："); int own_kingaku = stdIn.nextInt(); System.out.print("商品の値段は："); int item_price = stdIn.nextInt(); while (own_kingaku < item_price) { System.out.print("この所持金では購入不可です。もう一度買い物金額を入力して下さい："); item_price = stdIn.nextInt(); } //所持金の貨幣枚数((金額、枚数)の組み合わせ)を計算 Map<Integer, Integer> own_kingaku_maisu_map = getKaheiMaisuMap(own_kingaku); /* System.out.println("\n所持金の貨幣mapは"); for (int money : kahei_arr) { System.out.println(money + "円: " + own_kingaku_maisu_map.get(money) + "枚"); } System.out.println(); */ //支払額の全パターンについて、おつりの金額と枚数を求めていく SortedMap<Integer, Integer> oturi_maisu_kingaku_map = new TreeMap<Integer, Integer>(); //<お釣りの枚数、お釣りの金額> for (Integer shiharai_kingaku : getKingakuList(own_kingaku_maisu_map)) { if (shiharai_kingaku >= item_price) { int oturi_kahei_maisu = 0; int oturi_kingaku = shiharai_kingaku - item_price; //おつりの枚数を求める for(Map.Entry<Integer, Integer> oturi_set : getKaheiMaisuMap(oturi_kingaku).entrySet()) { oturi_kahei_maisu += oturi_set.getValue(); //貨幣ごとの枚数を足していく } //おつりの枚数と金額をマップに格納 oturi_maisu_kingaku_map.put(oturi_kahei_maisu, oturi_kingaku); /* //支払い金額とそのお釣りの全てのパターン System.out.println("支払い額: " + shiharai_kingaku + " おつり: " + oturi_kingaku + " おつり枚数: " + oturi_kahei_maisu); */ } } System.out.println(); int oturi_min_maisu = oturi_maisu_kingaku_map.firstKey(); int oturi_min_kingaku = oturi_maisu_kingaku_map.get(oturi_min_maisu); System.out.println("最適支払額は、" + (item_price + oturi_min_kingaku)); System.out.println("そのときのお釣りは、" + oturi_min_kingaku); System.out.println("そのときのお釣りの数は、" + oturi_min_maisu); } }
こういう適度な難易度の問題ってなかなかないですね〜。
上記のURLのベストアンサーさんとは違い、泥臭い総当り方で算出しました（たぶん誰でも理解出来るでしょう・・）。コメントをはずすと全パターンがみれて面白いです。ベストアンサーさんの方がエレガントですが、いまいちロジックが理解出来ません。。今度じっくり解析してみます。
