;; достоинства монет
(def coins #{1 2 3 5})
(defn solve [f sum]
(cond
;; допустим, не существует ни одного способа разменять
;; отрицательную или нулевую сумму
(<= sum 0) 0
:else (let [subsums (map (partial - sum) coins)] ;для каждого
;достоинства
;монет формируем
;подзадачу
(+
;; решаем каждую подзадачу по отдельности и суммируем
;; результат
(reduce + 0 (map (partial f f) subsums))
;; если текущая сумма равна достинству одной из монет, то
;; мы нашли еще один способ размена
(if (coins sum) 1 0)))))
(println "---------- naive ----------")
(println
"result:" (time (solve solve
20))) (println "---------- memoized ----------")
(println
"result:" (time (solve
(memoize solve
) 20)))
Ozsg0LTQvtGB0YLQvtC40L3RgdGC0LLQsCDQvNC+0L3QtdGCCihkZWYgY29pbnMgI3sxIDIgMyA1fSkKCihkZWZuIHNvbHZlIFtmIHN1bV0KICAoY29uZAogICAgOzsg0LTQvtC/0YPRgdGC0LjQvCwg0L3QtSDRgdGD0YnQtdGB0YLQstGD0LXRgiDQvdC4INC+0LTQvdC+0LPQviDRgdC/0L7RgdC+0LHQsCDRgNCw0LfQvNC10L3Rj9GC0YwKICAgIDs7INC+0YLRgNC40YbQsNGC0LXQu9GM0L3Rg9GOINC40LvQuCDQvdGD0LvQtdCy0YPRjiDRgdGD0LzQvNGDCiAgICAoPD0gc3VtIDApIDAKCiAgICA6ZWxzZSAobGV0IFtzdWJzdW1zIChtYXAgKHBhcnRpYWwgLSBzdW0pIGNvaW5zKV0gO9C00LvRjyDQutCw0LbQtNC+0LPQvgogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIDvQtNC+0YHRgtC+0LjQvdGB0YLQstCwCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgO9C80L7QvdC10YIg0YTQvtGA0LzQuNGA0YPQtdC8CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgO9C/0L7QtNC30LDQtNCw0YfRgwogICAgICAgICAgICAoKwogICAgICAgICAgICAgOzsg0YDQtdGI0LDQtdC8INC60LDQttC00YPRjiDQv9C+0LTQt9Cw0LTQsNGH0YMg0L/QviDQvtGC0LTQtdC70YzQvdC+0YHRgtC4INC4INGB0YPQvNC80LjRgNGD0LXQvAogICAgICAgICAgICAgOzsg0YDQtdC30YPQu9GM0YLQsNGCCiAgICAgICAgICAgICAocmVkdWNlICsgMCAobWFwIChwYXJ0aWFsIGYgZikgc3Vic3VtcykpCiAgICAgICAgICAgICA7OyDQtdGB0LvQuCDRgtC10LrRg9GJ0LDRjyDRgdGD0LzQvNCwINGA0LDQstC90LAg0LTQvtGB0YLQuNC90YHRgtCy0YMg0L7QtNC90L7QuSDQuNC3INC80L7QvdC10YIsINGC0L4KICAgICAgICAgICAgIDs7INC80Ysg0L3QsNGI0LvQuCDQtdGJ0LUg0L7QtNC40L0g0YHQv9C+0YHQvtCxINGA0LDQt9C80LXQvdCwCiAgICAgICAgICAgICAoaWYgKGNvaW5zIHN1bSkgMSAwKSkpKSkKCihwcmludGxuICItLS0tLS0tLS0tIG5haXZlIC0tLS0tLS0tLS0iKQoocHJpbnRsbiAicmVzdWx0OiIgKHRpbWUgKHNvbHZlIHNvbHZlIDIwKSkpCihwcmludGxuICItLS0tLS0tLS0tIG1lbW9pemVkIC0tLS0tLS0tLS0iKQoocHJpbnRsbiAicmVzdWx0OiIgKHRpbWUgKHNvbHZlIChtZW1vaXplIHNvbHZlKSAyMCkpKQo=