Chapter 02

Problem 2: Even Fibonacci numbers

aoi.iter
aoi.iter
2022.06.23に更新

2022/06/21
2022/06/23 解答を修正

https://projecteuler.net/problem=2

問題

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

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
数列の項の値が 400 万以下のとき, 値が偶数の項の総和を求めよ.

考察

  • まずフィボナッチ数列を生成する関数が必要になる.
    リストか遅延シーケンスか、生成する数列の構造を確する必要がある.
    値が 400 万以下になるフィボナッチ数列の長さはそこまで大きくないのでこの設問にはリストで十分だが、
    フィボナッチ数列の生成は多用するので、より柔軟な遅延シーケンスを利用する

  • フィボナッチ数列を生成したならば、値が 400 万未満になるまで抜き出す(take-while)

  • 400 万未満のフィボナッチ数列から偶数のものをフィルタする

  • 総和をとる

解答

; https://projecteuler.net/problem=2
(use util.stream)

(define fib
  (stream-append (stream 1 1)
                 (stream-delay
                  (stream-map +
                              fib
                              (stream-cdr fib)))))

(stream->list (stream-take fib 10))
;=> (1 1 2 3 5 8 13 21 34 55)
; 設問では数列の最初の2項を1,2にしているためズレている
; 偶数値の項に影響ないので、一般的な1, 1を最初の項にした

(define (answer)
  (stream-fold +
              0
              (stream-filter even?
                              (stream-take-while
                              (lambda (x) (< x 4000000))
                              fib))))
(answer)
;=> 4613732

解説

今回実装したフィボナッチ数列の生成を Haskell で表現すると以下のようになる

fib = 1:1:zipWith (+) fib (tail fib)

ある数列とそれを一つずらした(cdr した)数列を足し合わせるイメージでフィボナッチ数列ができる

  [1, 1, 2, 3, 5, 8, 13]
+ [   1, 1, 2, 3, 5,  8]
------------------------
  [1, 2, 3, 5, 8, 13, 21] <= フィボナッチ数列

感想

関数型言語にありがちな zipWith 関数は、scheme だと map が使える
scheme の方式のほうが好き

2021/06/23 修正

コメントから、06/21 時点のコードに問題がある指摘をいただいた。

修正前のフィボナッチ遅延ストリームは以下になっていた

(define fib
  (stream-append (stream 1 1)
                 (stream-map +
                             fib
                             (stream-cdr fib))))

これでは、fibの宣言が完了する前からfibを評価するために、未初期化エラーuninitialized variable: fibが発生する

REPL 駆動開発をしていると、試行錯誤の結果が残っているせいで正常動作してしまうことがある
今回の場合は、(うまく再現できなかったが)fibが定義された状態で上記fibを定義したことで REPL 上で正常動作してしまった。
実装をひと段落したら REPL をリスタートして、上記問題が発生していないか確認する必要がある。