Путь-путь для решения Фибоначчи - PullRequest
Новая
       33

Путь-путь для решения Фибоначчи

11 голосов
/ 09 марта 2009

Я хотел попробовать выучить Лисп, но очень быстро сдался. Я решил попробовать еще раз. Я смотрю на Задача 2 в Project Euler - найти сумму всех четных чисел Фибоначчи до 4 миллионов.

Я написал следующий код, который работает, но все виды безобразны. Главным среди них является тот факт, что это так медленно - потому что он все время делает наивную рекурсию.

Когда я писал эту программу на Python, я строил список по моим подсчетам и никогда не пересчитывал числа. Я знаю, что мог бы сделать это здесь (как-то), но это не соответствует духу функционального программирования. Я сдался после # 3, когда я достиг предела глубины рекурсии и мне пришлось переписать свой код, чтобы использовать цикл вместо рекурсии.

Итак, я полагаю, мои вопросы:

  1. Что такое «правильный, неумелый способ» решить эту проблему?
  2. Как вы совмещаете рекурсию и понятие «просто вычислить все» с практическим пределом вычисления всего?
  3. Есть ли какие-нибудь рекомендации для изучения lisp кроме The Little Schemer и Project Euler?

А вот и мой код: 

 (defun fib(i)
   (if (= i 1)                   ;Could rewrite this as a case statement
     1
     (if (= i 2)
       1
       (+ (fib (- i 1)) (fib (- i 2))))))

 (defun solve(i)
   (let ((f (fib i)))            ;Store result in local variable
     (print f)                   ;For debugging
     (if (< 4000000 f)
       0                         ;return
       (if (= 0 (mod f 2))
         (+ f (solve (+ i 1)))   ;add number
         (solve (+ i 1))))))     ;don't

 (print (solve 1))

Ответы [ 14 ]

0 голосов
/ 27 февраля 2019

;;; Я пытаюсь написать код как предложение @ PESTO

(defun Fibo-Test (n / one_prior two_prior curr sum i)

(setq i 2) (setq one_prior 1 two_prior 1 )

(конд

((= n 0) (заданная сумма 0) )

((= n 1) (заданная сумма 1) )

((= n 2) (заданная сумма 1) )

(Т

(while (и ( ;;; преобразовать в вещественное число

(setq sum (+ (float one_prior) (float two_prior)))

(setq i (1+ i))

(заданная сумма) (SETQ
one_prior two_prior two_prior curr
)

); конец пока

); конец конд (T)

); end cond

(princ (strcat "\ nF (" (itoa i) ") =" (сумма RTOS) "."))

(PRINC)

); конечная функция Fibo-Test

0 голосов
/ 18 марта 2009

Простой, эффективный способ создания списка чисел Фибоначчи: 

(defun fibs (n &optional (a 1) (b 1))
  (loop repeat n 
        collect (shiftf a b (+ a b))))

(shiftf) занимает любое количество мест и, наконец, значение. Каждому месту присваивается значение следующей переменной, а последняя переменная принимает значение, которое следует за ней. Возвращает значение первого места. Другими словами, он сдвигает все значения, оставленные на единицу.

Однако вам не нужен полный список (вам нужны только четные числа) и вам вообще не нужен список (вам нужна только сумма), так что это можно напрямую включить в функцию. Каждое третье число Фибоначчи четное, поэтому ... 

(defun euler-2 (limit &optional (a 1) (b 1))
  (loop for x upfrom 1
        until (> a limit)
        if (zerop (mod x 3)) 
           sum a
        do (shiftf a b (+ a b))))
0 голосов
/ 11 марта 2009 
(defun fib (x &optional (y 0) (z 1))
           (if (< x z)
               nil
               (append (list z) (fib x z (+ y z)))))

CL-USER> (reduce #'+ (remove-if-not #'evenp (fib 1000000)))
0 голосов
/ 09 марта 2009

Смотрите видео и текст по адресу: http://groups.csail.mit.edu/mac/classes/6.001/abelson-sussman-lectures/

Страница:
...