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个(即,数字的平方加起来小于目标的数字).

其实这种现象并不局限于1秒- decompose_aux(8, 2)回报nil,而(decompAux 8 2)回报(2 2)-但事实上,你总是可以倒计时点在哪里i是1那个手段decompAux保证返回的答案对任何积极nb和rac投入(这可能涉及很多1S答案) .

这里有一个相当直接的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]