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

2009年12月 3日 (木)

Project euler : Problem 2 〜 フィボナッチ数

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

 皆様ご存知の Fibonacci 数の問題ですが、この問題で提示されているフィボナッチ数は "1, 1, 2, 3, 5 ..." といった一般的なものではなく、"1, 2, 3, 5 ..." といったふうに、一つずれた形になっています。(まあ、答えには影響はありませんが……)
 まずは、再帰的な定義によるものから……同じ計算を繰り返しやっているので遅いです。

fibonacci :: Integer -> Integer fibonacci 1 = 1 fibonacci 2 = 2 fibonacci n = fibonacci (n - 2) + fibonacci (n - 1) problem002 :: Integer -> Integer problem002 n = sum [x | x <- fibList, even x] where fibList = takeWhile (< n) $ map fibonacci [1 ..] main = print $ problem002 4000000

 次は反復的にフィボナッチ数列を求めるもの……これはそこそこ速いのでは?

fibonacci :: [Integer] fibonacci = fib 1 2 where fib a b = a : fib b (a + b) problem002 :: Integer -> Integer problem002 n = sum [x | x <- takeWhile (< n) fibonacci, even x] main = print $ problem002 4000000

 Haskell では比較的簡単な定義で無限の数列を扱えるのが魅力的ですね。

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

Haskell」カテゴリの記事

Project Euler」カテゴリの記事

コメント

コメントを書く

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

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

トラックバック

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

この記事へのトラックバック一覧です: Project euler : Problem 2 〜 フィボナッチ数:

« Project Euler : Problem 1 ~ 今度は Haskell で | トップページ | 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            
フォト

最近のトラックバック

無料ブログはココログ