scheme - 以降序生成卢卡斯数列表(使用 let)

Question

Lucas 数与 Fib 数相似，只是它以 2 而不是 1 开头:

 2, 1, 3, 4, 7, 11, 18,

我想编写一个函数，以降序生成卢卡斯系列数字列表，直到第 n 个元素为止。

我写了这个，但我追踪了它，它太慢了，无法在我的列表构建功能中实现。

(defun lucas (n)
  (cond 
    ((equal n 0) 2)
    ((equal n 1) 1)
    (t (+ (lucas (- n 1))
          (lucas (- n 2))))))

这是我为列表函数编写的内容。问题是 (lucas n) 非常慢，我不想在我已经在使用 let 时调用辅助函数。

(defun lucas-list(n)
  (cond
   ((equal n 0) (cons n nil))
   (t (let ((n1 (lucas n)) (n2 (lucas(- n 1))))
        (cons n1 (lucas-list n2))))))

我要实现的目标:

(lucas-list 3) => '(4 3 1 2))

感谢任何建议/帮助

Answer 1

( pseudo -)线性时间 algorithm for the Fibonacci numbers可以很容易地扩展到卢卡斯数:

(define (lucas n)
  (let loop ((a 2) (b 1) (n n))
    (if (= n 0)
      a
      (loop b (+ a b) (- n 1)))))

这可以映射到整数上以获得所需的结果:

> (map lucas '(0 1 2 3 4 5))
(2 1 3 4 7 11)
> (reverse (map lucas '(0 1 2 3 4 5)))
(11 7 4 3 1 2)

但实际上有一个更快的方法:如果您意识到上述算法在计算 Lᵢ 之前先计算 Lᵢ₋₁ 和 Lᵢ₋₂，那么将它们保存在列表中应该可以节省大量时间。这给出了:

(define (lucas n)
  (let loop ((a 2) (b 1) (n n) (l '()))
    (if (= n 0)
      l
      (loop b (+ a b) (- n 1) (cons a l)))))

在行动中:

> (lucas 20)
(9349 5778 3571 2207 1364 843 521 322 199 123 76 47 29 18 11 7 4 3 1 2)