按递减顺序生成Lucas数列表(使用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))))))

下面是我为list函数编写的内容。问题是(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

(伪-)线性时间Fibonacci数的算法可以很容易地扩展到Lucas数：

(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)

Answer 2

优化fibonacci类型过程的一种优雅方法是使用memo函数缓存以前计算过的每个结果：

在球拍中(使用哈希表；一般，音阶非常好)

(define (memoize fn)
  (let ((cache (make-hash)))
    (lambda arg (hash-ref! cache arg (lambda () (apply fn arg))))))

在R6RS方案中(效率较低，泛型较少，但在这方面仍然很好)

(define (memoize proc)
  (let ([cache '()])
    (lambda (x)
      (cond
        [(assq x cache) => cdr]
        [else (let ([ans (proc x)])
                (set! cache (cons (cons x ans) cache))
                ans)])))) 

应用于lucas过程(这类似于Python装饰器)：

(define lucas
  (memoize
   (lambda (n)
     (cond
       ((= n 0) 2)
       ((= n 1) 1)
       (else   (+ (lucas (- n 1)) (lucas (- n 2))))))))

而list过程利用使用累加器会逆转结果这一事实，变成：

(define (lucas-list n)
  (let loop ((i 0) (res null))
    (if (= i n)
        res
        (loop (+ i 1) (cons (lucas i) res)))))

测试：

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

Answer 3

不如：

(defun lucas-list (n)
  (if (equal n 0)
      '()
      (cons (lucas n) (lucas-list (- n 1)))))