Составление списка чисел Лукаса в порядке убывания (используя let)

Question

Числа Лукаса похожи на числа Фибоначчи, за исключением того, что они начинаются с 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))))))

Вот что я написал для функции списка. Проблема в том, что (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

( Псевдо -) алгоритм линейного времени для чисел Фибоначчи можно легко распространить на числа Лукаса:

(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

Элегантный способ оптимизировать процедуры типа Фибоначчи с помощью функции memoïze, которая кэширует каждый ранее вычисленный результат:

В Racket (с использованием хеш-таблиц; общий, очень хорошо масштабируется)

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

и процедура списка, использующая преимущество того факта, что использование аккумулятора обращает результат, становится:

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

Answer 4

(defun lucas-list-decreasing (n &aux (table (make-hash-table)))
  (labels ((lucas-int (n)
              (or (gethash n table)
                  (setf (gethash n table)
                        (cond ((equal n 0) 2)
                              ((equal n 1) 1)
                              (t (+ (lucas-int (- n 1))
                                    (lucas-int (- n 2)))))))))
    (lucas-int n)
    (loop for i downfrom (1- n) downto 0
          collect (gethash i table))))

Или же:

(defun lucas (n &aux (table (make-hash-table)))
  (labels ((lucas-int (n)
             (or (gethash n table)
                 (setf (gethash n table)
                       (cond ((equal n 0) 2)
                             ((equal n 1) 1)
                             (t (+ (lucas-int (- n 1))
                                   (lucas-int (- n 2)))))))))
    (values (lucas-int n)
            table)))

(defun lucas-list-decreasing (n)
  (multiple-value-bind (value table)
      (lucas n)
    (declare (ignore value))
    (loop for i downfrom (1- n) downto 0
          collect (gethash i table))))