如何在Lisp中生成一系列Pell编号而不是特定的编号

Question

如何使用缺点或其他方式打印佩尔编号列表直到第N个编号？

(defun pellse (k)
   (if (or (zerop k) (= k 1))
       k
   (+ (* 2 (pellse (- k 1)))
      (pellse (- k 2)))))
 (print (pellse 7))

Answer 1

这是一种以非指数方式进行的方法：

(defun pells (n)
  (loop repeat n
    for current = 0 then next
    and next = 1 then (+ (* 2 next) current)
    collect current))

给定前两个元素，计算第n个元素的时间复杂度为O（log（P _n）），其中P _n是第n个佩尔数；您需要登录（P _ñ的答案和日志（）位P _ñ的加法）操作。实际上，我们不需要计算出P _n是什么：它由简单的线性递归关系定义，因此解必须是指数形式，因此log（P _n）= O（n）。因此，计算前n个佩尔数的复杂度为O（n * n）= O（n ²）。

一个^{[ * ]}不能比O（n ²）更好，因为一个人必须写O（n ²）位来表示所有这些数字。

^{[ * ]}尽管我对此非常怀疑，但从理论上讲，它可能通过某种方式共享数据以更紧凑的方式表示列表。

Answer 2

这是解决此问题的一种方法，该方法通过定义无限的Pell数流而起作用。这是基于SICP（尤其是第3.5节）中提出的想法。每个人都应该读这本书。

首先，我们需要定义一个构造，让我们谈论无限的数据结构。为此，我们会延迟评估除有限部分以外的所有部分。因此，从一个名为的宏开始，该宏delay会延迟对表单的求值，并返回一个“ promise”（当然是函数），而一个名为的函数force将迫使系统兑现其承诺：

(defmacro delay (form)
  ;; Delay FORM, which may evaluate to multiple values.  This has
  ;; state so the delayed thing is only called once.
  (let ((evaluatedp-n (make-symbol "EVALUATEDP"))
        (values-n (make-symbol "VALUES")))
    `(let ((,evaluatedp-n nil) ,values-n)
       (lambda ()
         (unless ,evaluatedp-n
           (setf ,evaluatedp-n t
                 ,values-n (multiple-value-list
                            (funcall (lambda () ,form)))))
         (values-list ,values-n)))))

(defun force (promise)
  ;; force a promise (delayed thing)
  (funcall promise))

（出于我们的目的，此实现有些复杂，但这是我必须要做的。）。

现在，我们将使用delay定义流有潜在conses之外的无限链。有这些操作对应于cons上的操作，但前缀为stream-，并且有一个null-stream对应于的对象()（实际上在此实现中是相同的对象）。

(defmacro stream-cons (car cdr)
  ;; a cons whose cdr is delayed
  `(cons ,car (delay ,cdr)))

(defun stream-car (scons)
  ;; car of a delayed cons
  (car scons))

(defun stream-cdr (scons)
  ;; cdr of a delayed cons, forced
  (force (cdr scons)))

(defconstant null-stream
  ;; the empty delayed cons
  nil)

(defun stream-null (stream)
  ;; is a delayed cons empty
  (eq stream null-stream))

现在定义一个pell-stream返回佩尔数字流的函数。此函数手工制作流的前两个元素，然后使用生成器制作其余元素。

(defun pell-stream ()
  ;; A stream of Pell numbers
  (labels ((pell (pn pn-1)
             (let ((p (+ (* 2 pn) pn-1)))
               (stream-cons p (pell p pn)))))
    (stream-cons 0 (stream-cons 1 (pell 1 0)))))

现在我们可以简单地反复stream-cdr计算佩尔数。

(defun n-pell-numbers (n)
  (loop repeat n
        for scons = (pell-stream) then (stream-cdr scons)
        collect (stream-car scons)))

现在

> (n-pell-numbers 20)
(0
 1
 2
 5
 12
 29
 70
 169
 408
 985
 2378
 5741
 13860
 33461
 80782
 195025
 470832
 1136689
 2744210
 6625109)

注意，实际上，它pell-stream可以是一个全局变量：它不必是一个函数：

(defparameter *pell-stream*
  (labels ((pell (pn pn-1)
             (let ((p (+ (* 2 pn) pn-1)))
               (stream-cons p (pell p pn)))))
    (stream-cons 0 (stream-cons 1 (pell 1 0)))))

(defun n-stream-elements (stream n)
  (loop repeat n
        for scons = stream then (stream-cdr scons)
        collect (stream-car scons)))

如果我们定义一些基准测试程序：

(defun bench-pell (n)
  (progn (n-stream-elements *pell-stream* n) n))

然后有趣的是，这显然是一个线性过程（因为后面的元素变大，所以它放慢了速度，因为数字变大，因此对它们的操作需要很长时间），并且有条件地实现promise会使它在第一个之后更快得多。迭代（以保持大量bignum为代价）：

> (time (bench-pell 100000))
Timing the evaluation of (bench-pell 100000)

User time    =        2.020
System time  =        0.803
Elapsed time =        2.822
Allocation   = 1623803280 bytes
441714 Page faults
100000

> (time (bench-pell 100000))
Timing the evaluation of (bench-pell 100000)

User time    =        0.007
System time  =        0.000
Elapsed time =        0.006
Allocation   = 1708248 bytes
0 Page faults
100000