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 の方法でどのように記述しますか? ループの繰り返しではなく、マップ、リデュースなどを使用したもの。

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

この種の問題に対しては、 iterateがloopを使用する良い代替手段となることがよくあります。この場合、ソース アルゴリズムのかなり透過的な変換につながります。

(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 に答える