04/06/09 14:50
fibonacci 数列について質問です。
これを関数型の記述のまま、計算量を減らすことはできないでしょうか？
まず、定義どおりに関数型で記述してみました。
(define (fib x)
(if (< x 2)
1
(+ (fib (- x 1)) (fib (- x 2)))))
これだと、定義がそのままコードになっていて、とてもわかりやすいのですが、
x の小さな項を何度も計算しなおすので、x が大きくなると計算量が膨れ
上がってしまいます。
Chez Scheme では x=35 ぐらいが限界でした。
手続き型で、小さい項をまず求めて、それをもとに大きな項を求めるように書くと、
計算量がはるかに少なくて済むのですが、わかりづらくなります。
定義がそのままコードになっている、関数型の記述とはだいぶ違います。
(define (fib2 n)
(if (< n 2)
1
(do ((x1 1 (+ x1 x0))
(x0 1 x1)
(m 2 (+ m 1)))
((<= n m) (+ x1 x0)))))