解决斐波那契数列的 Lisp 方法

Question

我想尝试学习 Lisp，但我很快就放弃了。 我想我会再试一次。 我正在查看 Project Euler 的问题 2 - 求总和400 万以下的所有斐波那契数列。

我写了下面的代码，它可以工作，但是很丑陋。 其中最主要的是它太慢了——因为它一直在进行简单的递归。

当我用 Python 编写这个程序时，我在计算时建立了一个列表，并且从未重新计算数字。 我知道我可以在这里（以某种方式）做到这一点，但这似乎不符合 lisp 和函数式编程的精神。 在#3 之后，当我达到递归深度限制并且不得不重写我的代码以使用循环而不是递归时，我放弃了。

所以我想我的问题是：

1. 解决这个问题的“正确的、口齿不清的方法”是什么？
2. 您如何协调递归和“仅计算所有内容”的概念与计算所有内容的实际限制？
3. 除了《小阴谋家》和《欧拉计划》之外，还有什么学习 lisp 的推荐吗？

这是我的代码：

 (defun fib(i)
   (if (= i 1)                   ;Could rewrite this as a case statement
     1
     (if (= i 2)
       1
       (+ (fib (- i 1)) (fib (- i 2))))))

 (defun solve(i)
   (let ((f (fib i)))            ;Store result in local variable
     (print f)                   ;For debugging
     (if (< 4000000 f)
       0                         ;return
       (if (= 0 (mod f 2))
         (+ f (solve (+ i 1)))   ;add number
         (solve (+ i 1))))))     ;don't

 (print (solve 1))

Answer 1

http://fare.tunes.org/files/fun/fibonacci.lisp有一个解决斐波那契数的演练，逐步提高实现的时间和内存性能。

Answer 2

Memoization 是一种将结果缓存到函数的方法，以避免重新计算中间结果以及结束。 记忆化基本上意味着您第一次使用一些参数调用函数，计算答案并返回它，并缓存该答案； 对于具有相同参数的函数的后续调用，只需返回缓存的值。

在 Lisp 中，您可以轻松地使用高阶函数和宏来透明地记忆函数。 Clojure 将 memoize 作为包含的标准函数。 另请参阅 On Lisp 的第 65 页，了解 memoize. Clojure 中的情况如下：

(defn fib-naive [i]
  (if (or (= i 1) (= i 2))
    1
    (+ (fib-naive (- i 1)) (fib-naive (- i 2)))))

(def fib-memo
     (memoize (fn [i]
                (if (or (= i 1) (= i 2))
                  1
                  (+ (fib-memo (- i 1)) (fib-memo (- i 2)))))))

user> (time (fib-naive 30))
"Elapsed time: 455.857987 msecs"
832040
user> (time (fib-memo 30))
"Elapsed time: 0.415264 msecs"
832040
user> 

如果您对大整数调用它，仍然可能导致堆栈溢出。 例如，立即执行 (fib 10000) 将会破坏堆栈，因为它仍然需要非常深入地递归（一次）。 但是，如果您首先填充缓存，则不再需要深度递归，并且可以避免这种情况。 只需首先执行此操作（在 Clojure 中）：

(dorun (map fib-memo (range 1 10000)))

就足以让您毫无问题地执行 (fib 10000) 。

（计算斐波那契数列的具体主题最近出现在 Clojure 邮件列表 那里有一个基于 Lucas 号码的解决方案。 我一点也不明白，但据说它比简单的算法快 40 倍。）

Answer 3

使用尾递归而不是朴素递归。 大多数 Lisp 实现应该执行尾调用优化； 不再有递归深度限制。

除此之外，尝试从列表和可以在这些列表上执行的抽象操作的角度来思考事物。 需要考虑的两个更相关的操作：

• filter
• fold

关于其他 Lisp 资源：

• Common Lisp—On Lisp
• 方案—计算机程序的结构和解释

更新：
尾递归方案 fib 函数：

(define (fib n)
  (fib-tr n 1 0))

(define (fib-tr n next result)
  (cond ((= n 0) result)
        (else (fib-tr (- n 1) (+ next result) next))))

Answer 4

(let ((a 1) (b 1))
  (flet ((nextfib ()
           (prog1 a
             (psetf a b b (+ a b)))))
    (loop for fib = (nextfib)
          while (<= fib 4000000)
          when (evenp fib)
            sum fib)))

上面定义了一个函数 NEXTFIB ，它将为每次调用生成下一个斐波那契数。 LOOP 对偶数结果求和，上限为 4000000。PROG1

返回其第一个子表达式的值。 PSETF 将 a 和 b 设置为“并行”。

这是一种常见的模式。 有一个生成器函数，可以重复调用它，过滤结果并将它们组合起来。

Answer 5

解决这个问题的方法是自下而上地工作，逐一生成每个斐波那契项，如果是偶数，则将其添加到总和中，一旦达到 400 万阈值就停止。 我的 LISP 很生锈，所以这里是伪代码：

one_prior = 1
two_prior = 1
curr = 2
sum = 0
while curr < 4000000000
  if curr % 2 == 0
    sum = sum + curr
  two_prior = one_prior
  one_prior = curr
  curr = one_prior + two_prior

Answer 6

达尼奥的回答将对性能问题有很大帮助。

这是对您的风格的简短批评：

 (defun fib(i)
   (if (= i 1) ;//Could rewrite this as a case statement
     1
     (if (= i 2)
       1
       (+ (fib (- i 1)) (fib (- i 2)))
     )
   )
 )

将嵌套 IF 重构为 COND。

不要将括号单独放在一行上。

 (defun solve(i)
   (let ((f (fib i))) ;//Store result in local variable
     (print f) ;//For debugging
     (if (

  使用 ZERO 更清晰。

         (+ f (solve (+ i 1))) ;//add number
         (solve (+ i 1)) ;//Don't

  你为什么把这些//放进去？   分号后跟一个空格就足够了。
       )

     )

   )

 )

 (print (solve 1))
  你最后的打印声明让我有点怀疑。   您是从文件还是从 REPL 运行该程序？   如果您执行前者，那么您应该考虑执行后者。   如果你选择后者，你只需说（解决 1）即可得到结果。

Answer 7

除了所有有用的答案之外，以下公式可能会提供更高的效率 - 以 O(Log(n)) 而不是 O(2^n) 的形式计算 Fn。 这必须与记忆相结合，并且是解决问题的坚实基础：

F(2*n) = F(n)^2 + F(n-1)^2

F(2*n + 1) = ( 2*F(n-1) + F(n) )   *   F(n)

Answer 8

为了扩展 Danio 的答案，文章位于 http://fare.tunes.org/files /fun/fibonacci.lisp 提供了两种使代码运行得更快的方法。 使用直接递归（尾调用或不）是 O(2^n) 并且非常慢。 困难在于每个值都会被一遍又一遍地计算。 你必须以不同的方式做事。 这两个建议是：

1. 使用迭代方法。

<代码>(defun bubble-fib (n) 
    (声明(优化(速度3)(安全0)(调试0))) 
    （检查类型 n 固定数） 
    （循环重复n 
    p = 0 q = 1 
    做（psetq pq 
          q (+ pq)) 
    最后（返回p））） 
  

2. 使用记忆化。 这意味着记住并回忆之前看到的值，而不是重新计算它们。 本文提供了一个可以执行此操作的 CL 包以及一些您可以自行执行此操作的代码。

Answer 9

我对“lisp 精神”的理解是让自己脱离任何固定的、教条的、自以为是的 lisp 精神观念，并使用最能反映解决问题所需的计算结构的 lisp 结构。 例如，

(defun euler2 (&optional (n 4000000))
  (do ((i 1 j)
       (j 2 (+ i j))
       (k 0))
      ((<= n i) k)
    (when (evenp i) (incf k i))))

如果你坚持递归，这里还有另一种方法：

(defun euler2 (&optional (n 4000000))
  (labels ((fn (i j k) 
             (if (<= n i) k (fn j (+ i j) (if (oddp i) k (+ k i))))))
    (fn 1 2 0)))

Answer 10

创建斐波那契数列表的简单、有效的方法：

(defun fibs (n &optional (a 1) (b 1))
  (loop repeat n 
        collect (shiftf a b (+ a b))))

(shiftf) 接受任意数量的位置，最后得到一个值。 每个位置都设置为下一个变量的值，最后一个变量采用其后面的值。 它返回第一个位置的值。 换句话说，它将所有值左移一位。

但是，您不需要完整的列表（您只需要事件），并且根本不需要列表（您只需要总和），因此可以直接将其添加到函数中。 每三个斐波那契数都是偶数，所以...

(defun euler-2 (limit &optional (a 1) (b 1))
  (loop for x upfrom 1
        until (> a limit)
        if (zerop (mod x 3)) 
           sum a
        do (shiftf a b (+ a b))))

Answer 11

查看视频和文本：http:// groups.csail.mit.edu/mac/classes/6.001/abelson-sussman-lectures/

Answer 12

(defun fib (x &optional (y 0) (z 1))
           (if (< x z)
               nil
               (append (list z) (fib x z (+ y z)))))

CL-USER> (reduce #'+ (remove-if-not #'evenp (fib 1000000)))

Answer 13

这是一个记忆版本。
在这种情况下，由于您必须计算每个斐波那契数，直到找到超过四百万的斐波那契数，因此使用封闭式解决方案不会有太大作用。

这种方法通过 let 创建一个词法环境； 创建字典fib-table
以及该环境中的函数 fib-memoed。 最终产品是 fib-table ，可以从 fib-memoed 访问，但不能从其他地方访问。

现在更关键的是：由于我们必须计算连续值的 fib 直到满足某些条件，因此我们在 fib 1 处启动求解器。 从这里开始，计算下一个小纤维
number 最多需要 2 次字典查找和一次加法：O(1) BOOM！

;; memoised fib function: make a hash table, then create                                      
;; the fib function in the lexical scope of the hash table                                    
(let ((fib-table (make-hash-table)))
  (setf (gethash 0 fib-table) 1)
  (setf (gethash 1 fib-table) 1)
  (defun fib-memoed (n)
    (let ((x (gethash n fib-table)))
      (cond ((not (null x))
             x)
            (t
             (let ((y (+ (fib-memoed (- n 1))
                         (fib-memoed (- n 2)))))
               (setf (gethash n fib-table) y)
               y))))))

(defun solve ()
  (let ((maxval 4000000))
    (labels ((aux (i acc)
               (let ((x (fib-memoed i)))
                 (cond ((> x maxval) acc)
                       ((evenp x)
                        (aux (1+ i) (+ x acc)))
                       (t (aux (1+ i) acc))))))
      (aux 1 0))))

Answer 14

;;; 我尝试按照@PESTO的建议编写代码

(defun Fibo-Test (n / one_prior Two_prior curr sum i)

(setq i 2)
(setq one_prior 1
两个_先验 1
)

(条件

((= n 0)
(setq 总和 0)
)

((= n 1)
(setq 总和 1)
)

((= n 2)
(setq 总和 1)
)

(T

(while (and (< in) (< sum (* 4 1e6)))

;;; 转换为 Real-num

(setq sum (+ (float one_prior) (float Two_prior)))

(setq i ( 1+ i))

(setq 当前总和)
（设置q
一个先验 两个先验
两个先前的当前
）

）； 结束同时

); 结束条件(T)

); end cond

(princ (strcat "\nF(" (itoa i) ") = " (RTOS sum) " . "))

(princ)

) ; 结束函数斐波纳奇检验