« Project Euler - Problem 1 : 今度は Scheme で…… | トップページ | Project Euler - Problem 3 : 素因数分解 »

2009年11月 9日 (月)

Project Euler - Problem 2 : 再帰的アルゴリズムと反復的アルゴリズム

問題はこちらをご覧ください。


この問題は、Scheme のコードを載せたことがあるのですが、改めて……

フィボナッチ数を求める場合、一番単純なのは定義に基づいて再帰的に求める方法です。(以下のコードはすべて Chez Scheme です)

;;; n 番目の Fibonacci 数を再帰的に求める。 (define fibonacci (lambda (n) (cond ([= n 1] 1) ([= n 2] 2) (else (+ (fibonacci (- n 2)) (fibonacci(- n 1)))))))

この手続きを使って、二つの方法を考えてみました。

;;; n 未満の偶数の Fibonacci 数の合計を出す。 (define problem-002-1 (lambda (n) (let loop ([i 1] [sum 0]) (let ([f (fibonacci i)]) (cond ([>= f n] sum) ([even? f] (loop (+ i 1) (+ sum f))) (else (loop (+ i 1) sum))))))) ;; > (time (problem-002-1 4000000)) ;; (time (problem-002-1 4000000)) ;; no collections ;; 3344 ms elapsed cpu time ;; 3411 ms elapsed real time ;; 2432 bytes allocated ;;; n 未満の Fibonacci 数列を作り、偶数だけを合計する。 (define problem-002-2 (lambda (n) (let loop ([i 1] [result '()]) (let ([f (fibonacci i)]) (if [>= f n] (apply + (filter even? result)) (loop (+ i 1) (cons f result))))))) ;; > (time (problem-002-2 4000000)) ;; (time (problem-002-2 4000000)) ;; no collections ;; 3324 ms elapsed cpu time ;; 3389 ms elapsed real time ;; 2848 bytes allocated

フィボナッチ数を求める場合、再帰的なアルゴリズムでは同じ計算を繰り返し行うので、非常に遅くなります。

実際、どちらも答えが出るまで約 3 秒かかっています。


もう一つの方法として、反復的なアルゴリズムでフィボナッチ数列を作ってから、そのリストを処理するというものがあります。

;;; n 未満の Fibonacci 数列を反復的に生成する。 (define fibonacci-list (lambda (n) (let loop ([a 1] [b 1] [result '()]) (if [>= a n] result (loop b (+ a b) (cons a result)))))) ;;; n 未満の Fibonacci 数列を求め、偶数だけを合計する。 (define problem-002-3 (lambda (n) (apply + (filter even? (fibonacci-list n))))) ;; > (time (problem-002-3 4000000)) ;; (time (problem-002-3 4000000)) ;; no collections ;; 0 ms elapsed cpu time ;; 0 ms elapsed real time ;; 496 bytes allocated

この場合、同じ計算を繰り替えさないので、非常に速く答えが出ます。

なお、"fibonacci-list" は内部処理を末尾再帰にしたかったのと、答えを出すのにリスト内の順序は関係なかったので、返ってくるリストはあえて「降順」のままになっています。


以前も書きましたが、繰り返しの処理には、"do" や "内部定義"、"letrec" などいろいろな方法があります。

でも、今回は自分の好みで、"named let" ばかりになってしまいました。たぶん、今後もそうなるんだろうなぁ……。

« Project Euler - Problem 1 : 今度は Scheme で…… | トップページ | Project Euler - Problem 3 : 素因数分解 »

Project Euler」カテゴリの記事

Scheme」カテゴリの記事

コメント

コメントを書く

コメントは記事投稿者が公開するまで表示されません。

(ウェブ上には掲載しません)

トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/112020/46721113

この記事へのトラックバック一覧です: Project Euler - Problem 2 : 再帰的アルゴリズムと反復的アルゴリズム:

« Project Euler - Problem 1 : 今度は Scheme で…… | トップページ | Project Euler - Problem 3 : 素因数分解 »

2016年7月
          1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31            
フォト

最近のトラックバック

無料ブログはココログ