fork download
copy 
  1. ;; достоинства монет
  2. (def coins #{1 2 3 5})
  3.  
  4. (defn solve [f sum]
  5.   (cond
  6.     ;; допустим, не существует ни одного способа разменять
  7.     ;; отрицательную или нулевую сумму
  8.     (<= sum 0) 0
  9.  
  10.     :else (let [subsums (map (partial - sum) coins)] ;для каждого
  11.                                                      ;достоинства
  12.                                                      ;монет формируем
  13.                                                      ;подзадачу
  14.             (+
  15.              ;; решаем каждую подзадачу по отдельности и суммируем
  16.              ;; результат
  17.              (reduce + 0 (map (partial f f) subsums))
  18.              ;; если текущая сумма равна достинству одной из монет, то
  19.              ;; мы нашли еще один способ размена
  20.              (if (coins sum) 1 0)))))
  21.  
  22. (println "---------- naive ----------")
  23. (println "result:" (time (solve solve 20)))
  24. (println "---------- memoized ----------")
  25. (println "result:" (time (solve (memoize solve) 20)))
  26.  
Success #stdin #stdout 3.23s 214656KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
---------- naive ----------
"Elapsed time: 2360.944131 msecs"
result: 190950
---------- memoized ----------
"Elapsed time: 1.872143 msecs"
result: 190950
https://ideone.com/9ioWX
language:
Clojure (clojure 1.10.0)
created:
12 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!