Euler : Problem 31

Posted by TAKAIY On 2011年5月22日日曜日 0 コメント
金種を組みあわせて2ポンドを作る問題。
金額の大きい順に個数を割りあてて樹形図を作るイメージ。

2£  1£  ... 

0 0
1
2

1 0
1

2

データ構造体は、
 <残りの金額> <金種ごとの枚数のリスト>
という感じ。


;;
;; Problem 31 : 2011/5/16
;; "Elapsed time: 604.414248 msecs"

;;data structure
(defstruct coin-table
:rest-amount
:coin-list)

(defn next-list [in-table coin]
(for [num (take-while #(<= (* % coin) (:rest-amount in-table)) (iterate inc 0))]
(struct coin-table
(- (:rest-amount in-table) (* coin num))
(assoc (:coin-list in-table) coin num))))

(loop [mid-flow (list (struct coin-table 200 {}))
coin-list [200 100 50 20 10 5 2]
result-list ()]
(if (empty? coin-list)
(concat result-list mid-flow)
(let [new-list (mapcat #(next-list % (first coin-list)) mid-flow)]
(recur (filter #(> (:rest-amount %) 0) new-list)
(rest coin-list)
(concat result-list (filter #(<= (:rest-amount %) 0) new-list))))))

;;

0 コメント:

コメントを投稿