Ruby 和 Clojure：算法相同（？）但结果不同

Question

我正在尝试将数字的平方分解为平方和：在 Ruby:

    def decompose(n)
      def decompose_aux(nb, rac)
        return [] if (nb == 0)
        i, l = rac, nil
        while (i >= Math.sqrt(nb / 2.0).to_i + 1) do
            diff = nb - i * i
            rac = Math.sqrt(diff).to_i
            l = decompose_aux(diff, rac);
            if l != nil then 
                l  << i; return l
            end
            i -= 1
        end
        l
    end  

    l = decompose_aux(n * n, Math.sqrt(n * n - 1).to_i);
    if l then return l else return nil end 
end

在 Clojure 中：

(defn decompAux [nb rac]
  (if (= 0 nb)
    ()
    (loop [i rac l nil]
      (let [diff (- nb (* i i)) rac (int (Math/sqrt diff)) l (decompAux diff rac)]
        (if (not= l nil) 
          (conj l i)
          (if (>= i 1)
            (recur (dec i) nil)
            nil))))))
(defn decompose [n]
  (let [l (decompAux (* n n) (- n 1))]
    (if l
      (reverse l)
      nil)))

在Ruby我得到

decompose(7654321) --> [6, 10, 69, 3912, 7654320].

在 Clojure 中：

(decompose 7654321) --> (1 1 2 3 11 69 3912 7654320)

Clojure 是对 Ruby 的跟踪，但结果不同。默认值在哪里？

Answer 1

这两个算法实际上并不相同。

不同之处在于，在 Clojure 中，您有不同的循环条件（正如 Tassilo Horn 在评论中指出的那样），并且您在计算中的不同点检查它。因此，Clojure 版本基本上可以根据需要将尽可能多的 1 添加到任何不是 "complete" 的候选结果（即，数字的平方加起来小于目标的数字）。

其实这个现象不限于1s – decompose_aux(8, 2) returns nil, 而(decompAux 8 2) returns (2 2) – 但是事实上，你总是可以倒数到 i 是 1 的那一点，这意味着 decompAux 可以保证 return 任何肯定的 nb 和 rac 输入（一个答案可能包含许多 1）。

这里是你的 Ruby 到 Clojure 的相当直接的翻译：

(defn decompose [n]
  (letfn [(decompose-aux [nb rac]
            (if (zero? nb)
              []
              (loop [i rac l nil]
                (if (>= i (inc (int (Math/sqrt (/ nb 2.0)))))
                  (let [diff (- nb (* i i))
                        rac  (int (Math/sqrt diff))
                        l    (decompose-aux diff rac)]
                    (if (some? l)
                      (conj l i)
                      (recur (dec i) l)))
                  l))))]       ; unnecessary line
    (decomp-aux (* n n) (int (Math/sqrt (dec (* n n)))))))

它与您示例中的 Ruby 版本匹配：

(decompose 7654321)
;= [6 10 69 3912 7654320]

Ruby 和 Clojure：算法相同（？）但结果不同

Ruby and Clojure: same algorith (?) but different results

ruby

clojure