[Project Euler] Problem 25 「1000桁のフィボナッチ数」

フィボナッチ数列は以下の漸化式で定義される:

F_n = F_n-1 + F_n-2 　(ただし F₁ = 1, F₂ = 1)

最初の12項は以下である.

F₁ = 1
F₂ = 1
F₃ = 2
F₄ = 3
F₅ = 5
F₆ = 8
F₇ = 13
F₈ = 21
F₉ = 34
F₁₀ = 55
F₁₁ = 89
F₁₂ = 144

12番目の項, F₁₂が3桁になる最初の項である.
1000桁になる最初の項の番号を答えよ.

フィボナッチ数を求めていけばよさそうです.

1. SICPの反復的プロセスを生成する手続きを参考にフィボナッチ数を求める.
2. フィボナッチ数を求める手続きの中で1000桁を超えたか判定する.

手続きは次のようになります.

(require srfi/1)

(define (decimal-format nbr)
  (define (loop ans n)
    (if (= 0 n)
        ans
        (loop (cons (remainder n 10) ans) (quotient n 10))))
  (loop () nbr))

(define (fib-list)
  (define (loop r a b)
    (if (<= 1000 (length (decimal-format a)))
        (reverse (cons a r))
        (loop (cons a r) b (+ a b))))
  (loop () 1 1))

計算してみます.

ようこそ DrRacket, バージョン 5.3.3 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (length (fib-list))
4782
>