时间戳

首页 > 解决方案 > 如何在 Lisp 中生成一系列 Pell 数字而不是特定数字

lisp - 如何在 Lisp 中生成一系列 Pell 数字而不是特定数字

问题描述

如何使用 cons 或其他方式打印Pell 数字列表直到第 N 个数字？

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

标签： lispcommon-lisp

解决方案

这是一种解决这个问题的方法，它通过定义无限的 Pell 数流来工作。这是基于SICP中提出的想法，特别是第 3.5 节。每个人都应该读这本书。

首先，我们需要定义一个让我们讨论无限数据结构的结构。我们通过延迟除有限部分之外的所有评估来做到这一点。因此，从一个称为delay延迟表单评估的宏开始，返回一个“承诺”（当然这是一个函数），以及一个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 上的操作，但前缀为stream-，并且有一个名为null-streamwhich 的对象对应于()（实际上在此实现中是同一个对象）。

(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返回 Pell 数流的函数。此函数手工制作流的前两个元素，然后使用生成器制作其余元素。

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

然后有趣的是，这显然本质上是一个线性过程（对于后面的元素它会变慢，因为数字变大，因此对它们的操作需要很长时间），并且承诺的有状态实现使其在第一个之后更快迭代（以保留相当多的 bignums 为代价）：

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

推荐阅读