将带有嵌套 for 循环的伪代码转换为 Clojure

Question

我想在 Clojure 中实现这个伪代码：

   function(n)                                       
       B[0] <-- 1                                      
       for m <-- 1 to n do                           
           B[m] <-- 0                                  
           for k <-- 0 to m - 1 do                     
               B[m] <-- B[m] − binom(m+1, k) * B[k]   
           B[m] <-- B[m]/(m+1)                               
       return B[n]

我的第一个想法是做这样的事情：

(defn foo [n]
  (if (= n 0)
    (int 1)
    (for [k (range 0 (- n 1))]
      (* (binom (+ n 1) k)
         (foo k)))))

但现在我卡住了，我不知道如何继续。当我尝试将它们翻译成 Clojure 时，嵌套循环让我很困惑。

我非常感谢有关如何在 Clojure 中编写这段代码的帮助，我感到有点迷茫。

提前致谢！

Answer 1

伪代码使用了大量 in-place 更新，这使得它有点难以阅读。但本质上，该代码计算一个数字列表，其中每个数字都是根据列表中的先前数字计算得出的。然后我们从列表中选择一个号码。

我会像这样实现这个算法

(defn compute-next-B [B]
  (let [m (count B)
        m+1 (inc m)
        terms (map-indexed (fn [k Bk] (- (* Bk (binom m+1 k)))) B)]
    (conj B (/ (apply + terms) m+1))))

(defn foo [n]
  (->> [1]
       (iterate compute-next-B)
       (drop n)
       first
       last))

伪代码的外循环是由(iterate compute-next-B ...)生成的惰性序列。伪代码的内部循环是惰性序列 terms.

中 (apply + terms) 内的迭代

Answer 2

给定的伪代码计算第 n 个 Bernoulli number。它使用所有先前的伯努利数来计算结果。与阶乘函数非常相似，这适用于递归算法，可以使用 memoize 来实现，以避免 re-computation 更早的数字：

(def factorial
  "Returns n!."
  (memoize (fn [n]
             (if (< 1 n)
               (* n (factorial (dec n)))
               1N))))

(def bernoulli
  "Returns the nth Bernoulli number."
  (memoize (fn [n]
             (if (zero? n)
               1
               (let [n!    (factorial n)
                     term  #(/ (* n! (bernoulli %))
                               (factorial %)
                               (factorial (- n % -1)))
                     terms (map term (range n))]
                 (reduce - 0 terms))))))

(map bernoulli (range 9)) ; => (1 -1/2 1/6 0N -1/30 0N 1/42 0N -1/30)

Answer 3

有些算法本质上是命令式的。如果那是最简单的解决方案，不要害怕编写命令式代码，而不是试图将算法“强制适应”到函数式风格。

该算法可以轻松地使用可变原子来存储 B 数组：

(defn factorial [x]
  (reduce * (range 2 (inc x))))

(defn binom [n k]
  (/ (factorial n)
    (factorial k) (factorial (- n k))))

(defn bernoulli [n]
  (let [B (atom (vec (repeat n 0)))] ; allocate B[0]..B[n-1] = zeros
    (swap! B assoc 0 1) ; B[0] = 1
    (doseq [m (range 1 (inc n))] ; 1..n
      (swap! B assoc m 0) ; B[m] = 0
      (doseq [k (range m)] ; 0..(m-1)
        (swap! B #(assoc % m  ; B[m] = ...
                    (-
                      (get % m) ; B[m]
                      (*
                        (binom (inc m) k)
                        (get % k)))))) ; B[k]
      (swap! B update m ; B[m] = B[m] ...
        #(/ % (inc m))))
    (get @B n)))

(dotest
  (dotimes [i 10]
    (spyx [i (bernoulli i)])))

结果


[i (bernoulli i)] => [0 1]
[i (bernoulli i)] => [1 -1/2]
[i (bernoulli i)] => [2 1/6]
[i (bernoulli i)] => [3 0N]
[i (bernoulli i)] => [4 -1/30]
[i (bernoulli i)] => [5 0N]
[i (bernoulli i)] => [6 1/42]
[i (bernoulli i)] => [7 0N]
[i (bernoulli i)] => [8 -1/30]
[i (bernoulli i)] => [9 0N]

您还可以将 with-local-vars 用于某些算法，甚至可以放入（可变的）Java 数组。您可以在 this mutable Java matrix example

中查看示例

将带有嵌套 for 循环的伪代码转换为 Clojure

Convert pseudo-code with nested for-loops to Clojure

clojure

translate

nested-loops