Problem 2 - ボクノス

ついでにProblem2もいっとこー。

フィボナッチ数列の項は前の2つの項の和である。最初の2項を 1, 2 とすれば、最初の10項は以下の通りである。
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
数列の項が400万を超えない範囲で、偶数の項の総和を求めよ。

フィボナッチか。

とりあえずふつうのフィボナッチ。

(define (fib n)
  (cond ((= n 1) 1)
        ((= n 2) 2)
        (else
          (+ (fib (- n 1)) (fib (- n 2))))))

(fib 10) ; 89

最初のインデックスは1から始まるらしい。

反復にする。

(define (fib n)
  (define (iter a b m)
    (if (= m n)
        a
        (iter b (+ a b) (+ m 1))))
  (iter 1 2 1))

(fib 10) ; 89

フィボナッチの反復は「先読み」と「ずらし」がポイント。

準備が出来たので、問題を解いてみよう〜。

(define (problem2 n)
  (define (iter a b acc)
    (if (>= a n)
        acc
        (iter b (+ a b) (if (= (modulo a 2) 0)
                            (+ a acc)
                            acc))))
  (iter 1 2 0))

(problem2 4000000) ; 4613732

案外少ないな。