如何使用 cons 或其他方式打印 Pell numbers 的列表直到第 N 个数?
(defun pellse (k)
(if (or (zerop k) (= k 1))
k
(+ (* 2 (pellse (- k 1)))
(pellse (- k 2)))))
(print (pellse 7))
最佳答案
以下是如何以一种不会呈指数增长的方式做到这一点:
(defun pells (n)
(loop repeat n
for current = 0 then next
and next = 1 then (+ (* 2 next) current)
collect current))
给定前两个元素,计算第 n 个元素的时间复杂度为 O(log(Pn)) 其中 Pn 为第n个佩尔数;您需要 log(Pn) 位的答案和 log(Pn) 操作的加法。我们实际上不需要计算出 Pn 是什么:它是由一个简单的线性递推关系定义的,所以解必须是指数的,所以 log(P n) = O(n)。因此计算第一个 n 佩尔数的复杂度是 O(n*n) = O(n2 ).
不能[*] 比 O(n2) 做得更好,因为必须写 O( n2) 位来表示所有这些数字。
[*] 虽然我非常怀疑这一点,但从理论上讲,它可能通过某种方式共享数据以某种更紧凑的方式表示列表。
关于lisp - 如何生成一系列 Pell 数而不是 Lisp 中的特定数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/55223694/