0

我尝试使用以下尾递归函数解决欧拉问题 2 ：

(defun fib (num)
  (labels ((fib-helper (num a b)
         (cond ((or (zerop num)
                    (eql num 1))
                a)
               (t (fib-helper (decf num)
                              (+ a b)
                              a)))))
    (fib-helper num 1 1)))


(defun sum-even-fib (max)
  (labels ((helper (sum num)
         (cond ((oddp num) (helper sum (decf num)))
               ((zerop num) sum)
               (t (helper (+ sum (fib num))
                          (decf num))))))
    (helper 0 max)))

现在，当我尝试使用该函数打印结果时

(defun print-fib-sum (max dir file)
  (with-open-file
      (fib-sum-str
       (make-pathname
         :name file
         :directory dir)
        :direction :output)
    (format fib-sum-str "~A~%" (sum-even-fib max))))

值为max，4000000我得到错误

     ("bignum overflow" "[Condition of type SYSTEM::SIMPLE-ARITHMETIC-ERROR]" nil)

从*slime-events*. 有没有其他方法可以处理号码并打印到文件中？

4

3 回答 3

3

首先，几个小问题：

  1. 使用time而不是top.

  2. Common Lisp 标准不需要尾递归优化。尽管许多实现都这样做了，但并非所有实现都优化了所有情况（例如，labels）。

  3. 您的算法是二次的，max因为它为所有索引分别计算第 n 个斐波那契数。您应该改为线性。

  4. 您正在计算偶数索引数的总和，而不是偶数数。

现在，您看到的算术错误：第 4,000,000 个斐波那契数相当大 - 大约1.6^4M~ 10^835951。它的长度约为2,776,968.

你确定你的 lisp 可以代表这么大的 bignums 吗？

于 2013-09-15T12:29:05.510 回答
0

所以我用下面的尾递归代码解决了 Euler #2：

(defun rev-sum-even-fib (max-val)
  (labels ((helper (sum a b)
             (cond ((oddp a)
                    (helper sum (+ a b) a)) 
                   ((> a max-val)
                    sum)
                   (t
                    (helper (+ sum a) (+ a b) a)))))
    (helper 0 1 0)))

在这里，算法是线性的，max并且在

(time (rev-sum-even-fib 4000000))

Real time: 3.4E-5 sec.
Run time: 0.0 sec.
Space: 0 Bytes

出于明显的原因，我省略了数字答案。

于 2013-09-15T14:16:47.953 回答
0

由于 CL 不承诺它支持 TCO（例如 JVM 上的 ABCL 不支持 TCO - 尾调用优化），因此将其可移植地编写为循环是有意义的：

(defun rev-sum-even-fib (max-val)
  (loop for a = 1 then (+ a b) and b = 0 then a
        until (> a max-val)
        when (evenp a) sum a))
于 2013-09-15T16:15:22.020 回答