2

例如，扩展欧几里得算法（引自 wiki）：

function extended_gcd(a, b)
    x := 0    lastx := 1
    y := 1    lasty := 0
    while b ≠ 0
        quotient := a div b
        (a, b) := (b, a mod b)
        (x, lastx) := (lastx - quotient*x, x)
        (y, lasty) := (lasty - quotient*y, y)       
    return (lastx, lasty)

我试过并得到：

 (defn extended-gcd 
  [a b]
  (loop [a a b b x 0 y 1 lx 1 ly 0]
     (if (zero? b)
      [lx ly]
      (recur b (mod a b)
             (- lx (* (int (/ a b)) x))
             (- ly (* (int (/ a b)) y))
             x y))))

我想我可以找到一种方法来翻译处理序列的循环。但是这个呢？我如何以clojure方式编写它？带有 map、reduce 等的东西，而不是循环重复。

4

2 回答 2

5

对于扩展的欧几里得算法，您可以使用简单的递归，这使得函数看起来非常优雅：

(defn extended-gcd [a b]
  (if (zero? b) [1 0]
    (let [[q r] [(quot a b) (rem a b)]
          [s t] (extended-gcd b r)] 
      [t (- s (* q t))])))

让我们尝试一下：

user=> (extended-gcd 120 23)
[-9 47]

并非所有问题都需要使用 map/reduce/sequence 来解决。我认为上述内容与(reduce + [1 2 3 4 5])您正在寻找的答案的“”类型一样，都是 Clojure 方式。

于 2013-08-28T12:55:01.873 回答
0

对于这种问题，迭代通常是使用循环的一个很好的替代方法。在这种情况下，它会导致源算法的翻译相当透明：

(defn extended-gcd [a b]
  (->> {:a a, :b b, :x 0, :y 1, :lx 1, :ly 0}
    (iterate 
      (fn [{keys [a b x y lx ly]}]
        (let [q (quot a b)]
          {:a b, :b (mod a b), :x (- lx (* q x)), :lx x, :y (- ly (* q y)), :ly y})))
    (drop-while #(not= 0 (:b %)))
    first
    ((juxt :lx :ly))))

也就是说，使用循环也是一种 Clojure 方式——我相信，避免它的警告是为了鼓励在更合适的地方使用更高级别的构造。

于 2013-08-29T14:26:56.200 回答