Project Euler Problem 2

400万未満のフィボナッチ数列の項において、偶数値になる項の和を求める。[=>原文和訳]

ごく普通に数列を作りながら判定して加算。

(require 'cl)
(defun problem002-1 ()
  (let ((N 4000000)
        (a 1) (b 2) (total 2))
    (while (< (setq c (+ a b)) N)
      (if (evenp c)
          (incf total c))
      (setq a b b c))
    total))

再帰版

(require 'cl)
(defun problem002-2 ()
  (let ((N 4000000))
    (defun sum-of-even-fibo (a b)
      (if (>= b N)
          0
        (if (evenp b)
            (+ b (sum-of-even-fibo b (+ a b)))
          (sum-of-even-fibo b (+ a b)))))
    (sum-of-even-fibo 1 2)))

　400万という提示を見て「これは再帰はキツイかな？」と思いましたが、やってみるとぜんぜん平気でした。再帰回数を調べるとたったの32回で解にたどり着いていました。指数関数ほどではありませんが、項の値の増加速度はかなりのものです。

高階関数を使う

　clパッケージにreduceがある。でもfilterはない。ググってみたら、どうもlisp界隈ではfilerという関数は標準では無いようですね。schemeではsrfi-1 で定義されていますが。
　無いものはしょうがないのでlamdaでやりくりしてみました。

(require 'cl)
(defun problem002-3 ()
  (let ((N 4000000))
    (defun make-fibo (a b)
      (if (>= b N)
          nil
        (cons b (make-fibo b (+ a b)))))
    (reduce #'(lambda (total elem)
                (if (evenp elem)
                    (+ total elem)
                  total))
            (make-fibo 1 1))))

さらにmapcar を使うとこんな書き方も。上と違うのはapply以降。

(require 'cl)
(defun problem002-4 ()
  (let ((N 4000000))
    (defun make-fibo (a b)
      (if (>= b N)
          nil
        (cons b (make-fibo b (+ a b)))))
    (apply #'+
           (mapcar #'(lambda (x)
                       (if (evenp x) x 0))
                   (make-fibo 1 1)))))

　前の２つと比べると、高階関数を使うパターンは、一度フィボナッチリストを作ってから処理を開始するので、パフォーマンス的には不利ですね。
　遅延リストほしい。