Problem 2の解答例を読む

これはショックだ。Problem 2の解答例も読んでみる。

問題は、

フィボナッチ数列の項は前の2つの項の和である。最初の2項を 1, 2 とすれば、最初の10項は以下の通りである。

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

数列の項が400万を超えない範囲で、偶数の項の総和を求めよ。

という問題。

フィボナッチ求めて、偶数だけ足せばいいとか思ったら、大間違いだ。

よく見ると

fib(0) = 1, fib(1) = 1としたとき、

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

偶数は3個目に現れる。

つまり、「偶数チェックなんてしなくていい」

ショックだ・・・。

書き直し

3倍速で回る。

(define (problem2 n)
  (letrec ((iter (lambda (a b c acc)
                   (if (> c n)
                       acc
                       (iter (+ b c) (+ c  b c) (+ b c  c b c) (+ acc c))))))
          (iter 1 1 2 0)))

(problem2 4000000) ; 4613732

traceすると驚く。

|(iter 1 1 2 0)
|(iter 3 5 8 2)
|(iter 13 21 34 10)
|(iter 55 89 144 44)
|(iter 233 377 610 188)
|(iter 987 1597 2584 798)
|(iter 4181 6765 10946 3382)
|(iter 17711 28657 46368 14328)
|(iter 75025 121393 196418 60696)
|(iter 317811 514229 832040 257114)
|(iter 1346269 2178309 3524578 1089154)
|(iter 5702887 9227465 14930352 4613732)
|4613732

えぇぇぇ・・・・たったこれだけ・・・。

感動した。すげー感動した。

追記

5番目は5の倍数になる。類題が出たら5倍の早さで解く自信がある。(ループ回数は減るけど実際の速度は変わらなかったり)