2012年3月16日金曜日

お釣りの枚数を最小にするための支払い方を考える

たまにありますよね。
お財布の中を見たらやたら1円玉とか10円玉が溜まっているとき。
え?ないですか?
お支払いの時ちゃんと考えてるんですね!

ってわけで、所持金からどういう払い方をすればお釣りの枚数が一番少なくなるのか。
言い換えればお財布の中を最適化するためには、どう支払えばいいのか。
っていうのを算出するプログラムを書いてみました。

プログラミング初心者への練習問題、プログラマ歴3年くらいの人への実力診断、などなど良い難易度かもしれません。

今回は自分の練習も兼ねてScalaで書いてみました。

[ payment.scala ]
   1: object Main {
   2:   
   3:   implicit val coins = List(1, 5, 10, 50, 100, 500, 1000, 5000, 10000)
   4:   
   5:   def main(args: Array[String]): Unit = {
   6:     if (args.length != 2) sys.exit(-1)
   7:     
   8:     val Array(pocket, price) = args.map(_.toInt)
   9:     
  10:     if (pocket < price) sys.exit(-1)
  11:     
  12:     val payment = getNumberOfCoinsOfPayment(pocket, price)
  13:     (coins zip payment).foreach(println)
  14:   }
  15:   
  16:   def getNumberOfCoinsOfPayment(pocket: Int, price: Int): List[Int] = (getNumberOfCoins(pocket), getNumberOfCoins(pocket - price)).zipped.map(_-_).map(minusToZero)
  17:   
  18:   def getNumberOfCoins(money: Int)(implicit coins: List[Int]): List[Int] = (coins :\ (money, List[Int]())) {case (c, (b, list)) => (b % c, (b / c) :: list)}._2
  19:   
  20:   def minusToZero(n: Int): Int = if (n > 0) n else 0
  21: }

[ 実行 ]


> scala payment.scala 2892 987


[ 結果 ]


(1,2)
(5,0)
(10,4)
(50,1)
(100,0)
(500,0)
(1000,1)
(5000,0)
(10000,0)

エラー処理とか結果表示とか適当すぎますが、まぁ大目に見てくださいw


突っ込みどころとかあったら、ぜひお願いします。

0 件のコメント:

コメントを投稿