时间戳

首页 > 解决方案 > 如何将此算法从 Ruby 转换为 Clojure？

ruby - 如何将此算法从 Ruby 转换为 Clojure？

问题描述

我一直在用 Ruby 解决一个编程任务，在完成它之后，我想我应该尝试应用我对 Clojure 的有限知识来实现​​同样的事情。我花了相当多的时间，但没有设法让它工作。

任务是：我们有一系列硬币类型和预期总和。用我们可以花费最少硬币数量的硬币类型来表示该总和的最佳方式是什么？因此，为了用硬币类型 [100, 50, 20, 10, 5] 表示 325，我们将产生以下结果：[100, 100, 100, 20, 5]。

这是我似乎可以正常工作的 Ruby 代码：

  def calc(coin_types, expected)
    calc_iter(coin_types.sort.reverse, expected, [])
  end

  def calc_iter(coin_types, expected, coins)
    sum = coins.sum

    return coins if sum == expected
    return nil if sum > expected

    coin_types.each do |type|
      result = calc_iter(coin_types, expected, coins + [type])
      return result if result
    end

    nil
  end

  # test
  calc([25, 10], 65) # should return [25, 10, 10, 10, 10]

现在我的两个失败的 Clojure 实现：

1）（它需要永远运行，所以我不得不杀死它）：

  (defn calc [types expected]
    (let [types (reverse (sort types))]
      (loop [coins []]
        (let [sum (count coins)]
          (if (= sum expected)
            coins
            (if (> sum expected)
              nil
              (first (filter #(not (nil? %))
                             (map #(recur (cons % coins))
                                  types)))))))))

2）（这个确实在合理的时间内完成但返回错误的结果）：

  (defn calc-iter [types expected coins]
    (let [sum (count coins)]
      (if (= sum expected)
        coins
        (if (> sum expected)
          nil
          (first (filter #(not (nil? %))
                         (map #(calc-iter types
                                          expected
                                          (cons % coins))
                              types)))))))

  (defn calc [types expected]
    (calc-iter (reverse (sort types))
               expected
               []))

标签： rubyalgorithmrecursionclojure

解决方案

这是一个简单的例子：

(def coin-values [100, 50, 20, 10, 5])

(defn coins-for-amount [amount]
  (loop [amount-remaining amount
         coins-avail      coin-values
         coins-used       []]
    (cond
      (zero? amount-remaining) coins-used ; success
      (empty? coins-avail) nil ; ran out of coin types w/o finding answer
      :else (let [coin-val              (first coins-avail)
                  num-coins             (quot amount-remaining coin-val)
                  curr-amount           (* coin-val num-coins)
                  amount-remaining-next (- amount-remaining curr-amount)
                  coins-avail-next      (rest coins-avail)
                  coins-used-next       (conj coins-used num-coins)]
              (recur amount-remaining-next coins-avail-next coins-used-next)))))


(coins-for-amount 325) => [3 0 1 0 1]
(coins-for-amount 326) => nil
(coins-for-amount 360) => [3 1 0 1]

请注意，在当前形式中，它不会累积尾随零。

更新

在我上面的原始答案中，我从未考虑过可能会选择像 [25 10] 这样棘手的硬币值，因此您需要 1 个季度和 4 个角钱才能达到总计 0.65 美元。上述算法会选择 2 个季度，然后被困在 0.15 美元的剩余资金中，并且只有一角硬币可用。

如果允许使用棘手的硬币值，则需要使用详尽的搜索算法。这是 Clojure 中的一个版本：

(ns tst.demo.core
  (:use tupelo.core demo.core tupelo.test))

(defn total-amount [coins-used]
  (let [amounts (mapv (fn [[coin-value num-coins]] (* coin-value num-coins))
                  coins-used)
        total   (reduce + amounts)]
    total))

(defn coins-for-amount-impl
  [coins-used coin-values amount-remaining]
  (when-not (empty? coin-values)
    (let [curr-coin-value       (first coin-values)
          coin-values-remaining (rest coin-values)
          max-coins             (quot amount-remaining curr-coin-value)]
      (vec (for [curr-num-coins (range (inc max-coins))]
             (let [coins-used-new       (conj coins-used {curr-coin-value curr-num-coins})
                   amount-remaining-new (- amount-remaining (* curr-coin-value curr-num-coins))]
               (if (zero? amount-remaining-new)
                 coins-used-new
                 (coins-for-amount-impl
                   coins-used-new coin-values-remaining amount-remaining-new))))))))

(defn coins-for-amount [coin-values amount]
  (remove nil?
    (flatten
      (coins-for-amount-impl {} coin-values amount))))

还有一些简短的单元测试：

(dotest
  (is= 48 (total-amount {25 1    ; quarter
                         10 2    ; dime
                         1  3})) ; penny


  (let [results (coins-for-amount [10 5 1], 17)]
    (is= results
      [{10 0, 5 0, 1 17}
       {10 0, 5 1, 1 12}
       {10 0, 5 2, 1 7}
       {10 0, 5 3, 1 2}
       {10 1, 5 0, 1 7}
       {10 1, 5 1, 1 2}]))

  (is= (coins-for-amount [25 10], 65)
    [{25 1, 10 4}] ))

因此，它会找到所有可能的组合以达到正确的总数。数硬币并找到硬币最少的解决方案（不要忘记领带！）留给读者作为练习。;)

推荐阅读