Можно ли сгенерировать более 40000 элементов Фибоначчи в Лиспе? - PullRequest
2 голосов
/ 04 декабря 2010

Я пытаюсь решить Project Euler вопрос 2 с помощью Lisp. Это рекурсивное решение уничтожает стек при выполнении, но я думал, что Lisp (используя clisp) распознает хвостовую рекурсию. Это вводится в верхний уровень.

(defun e2-problem (&optional (f1 1) (f2 1) (sum 0))  
   "Sum fibonacci sequence, even terms up to 4 million"

   (if (> f2 4000000) sum)
   (e2-problem f2 (+ f1 f2) (if (evenp f2) 
                                (+ sum f2) 
                               sum))

Правильно ли настроена моя реализация для оптимизации? Я полагаю, что это немного помешало бы моему образованию на Лиспе, если бы я не мог полагаться на идиоматическую рекурсию.

Ответы [ 4 ]

9 голосов
/ 04 декабря 2010

Рекурсия (или даже итерация) не нужна!

Каждое третье число Фибоначчи чётно:

1 1 2 3 5 8 13 21 34 55 89 144 ...

и поскольку каждое четное число Фибоначчи (выделено жирным шрифтом) является суммой двух предшествующих нечетных чисел Фибоначчи, сумма четных чисел Фибоначчи вплоть до F n - это ровно половина суммы всех чисел Фибоначчи до F n (если F n четно, конечно).

Теперь сумма первых n чисел Фибоначчи равна F n + 2 - 1. Это легко проверить по индукции: сумма первые n + 1 числа Фибоначчи - это F 1 + F 2 + ... + F n + F n + 1 , что равно F n + 2 - 1 + F n + 1 по гипотезе, что равно F n + 3 - 1 по определению чисел Фибоначчи.

Так что, если вы можете найти наибольшее N такое, что F 3 N ≤ 4 000 000, тогда запрашиваемая сумма будет (F 3 N + 2 - 1) / 2 * 1 083 *

(я оставлю вам остальные детали, но здесь все будет просто.)

4 голосов
/ 04 декабря 2010

1) Правильный синтаксис ошибка в коде:

(defun e2-problem (&optional (f1 1) (f2 1) (sum 0))  
   "Sum fibonacci sequence, even terms up to 4 million"
   (if (> f2 4000000) 
       sum   ;; here was a closing bracket 
       (e2-problem f2 (+ f1 f2) (if (evenp f2) 
                                    (+ sum f2) 
                                    sum))))  ;; 2 more brackets here

2) использование SBCL .CLISP не достаточно любезен, чтобы обнаружить хвостовую рекурсию.

3) использовать максимально возможную оптимизацию уровень:

(defun e2-problem (&optional (f1 1) (f2 1) (sum 0))  
   "Sum fibonacci sequence, even terms up to 4 million"
   (declare (optimize (debug 0)))  ;; optimization
   ... 
4 голосов
/ 04 декабря 2010

Я думал, что Лисп (используя clisp) распознает хвостовую рекурсию

Для среды, в которой устранение хвостовых вызовов является обязательным в схеме , но не в большинстведругие диалекты Лисп, такие как Common Lisp.

2 голосов
/ 04 декабря 2010

Ваш код реализует бесконечный цикл. Не заканчивается.

Использование LOOP:

(defun e2-problem-a (n)
  "Sum fibonacci sequence, even terms up to n"
  (loop for f1 = 1 then f2
        and f2 = 1 then (+ f1 f2)
        while (<= f2 n)
        when (evenp f2) sum f2))
...