如何在Lisp中生成一系列的Pell编号，而不是一个特定的编号 [英] How can I generate series of Pell numbers instead of a specific one in Lisp

问题描述

如何使用缺点或其他方式来打印编号的列表，直到第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( P _n ))，其中 P _n 是第 n 个Pell编号；您需要log( P _n )位来回答，并需要log( P _n )位来进行加法运算.实际上，我们不需要弄清楚 P _n 是什么:它是由一个简单的线性递归关系定义的，因此解必须是指数的，因此log( P _n )= O( n ).因此，计算第一个 n 个佩尔数的复杂度为O( n * n )= O( n ² ).

一个人不能 ^{[ * ]} 比O( n ² )做得更好，因为一个人必须写O( n ² )位代表所有这些数字.

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

How do I use cons or other way to print a list of Pell numbers till the Nth number?

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

解决方案

Here is how to do it in a way that won’t be exponential:

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

The time complexity to calculate the nth element given the two previous elements is O(log(P_n)) where P_n is the nth Pell number; you need log(P_n) bits for the answer and log(P_n) operations for the addition. We don’t actually need to work out what P_n is: It is defined by a simple linear recurrence relation so the solution must be exponential so log(P_n) = O(n). Therefore the complexity of calculating the first n Pell numbers is O(n*n) = O(n²).

One cannot^[*] do better than O(n²) as one must write O(n²) bits to represent all these numbers.

^[*] Although I very much doubt this, it might, in theory, be possible to represent the list in some more compact way by somehow sharing data.

这篇关于如何在Lisp中生成一系列的Pell编号，而不是一个特定的编号的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！