« Project Euler : Problem 24 ~ 順列 | トップページ | Project Euler : Problem 26 ~ 循環節の長さ »

2010年5月15日 (土)

Project Euler : Problem 25

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

 

 この問題は、特にに工夫はしていません。フィボナッチ数列を作って条件を満たすまで数え上げただけです。

fibonacci :: Integral a => [a] fibonacci = 1 : 1 : zipWith (+) fibonacci (tail fibonacci) problem025 :: Int problem025 = count fibonacci where limit = 10 ^ (1000 - 1) count (x : xs) | x > limit = 1 | otherwise = 1 + count xs main = print problem025

 "takeWhile" を使ったバージョンも考えてみました。

fibonacci :: Integral a => [a] fibonacci = 1 : 1 : zipWith (+) fibonacci (tail fibonacci) problem025 :: Int problem025 = 1 + length fibonacci' where limit = 10 ^ (1000 - 1) fibonacci' = takeWhile (< limit) fibonacci main = print problem025
 実際の問題は「1000 桁になる最初の項」を探すのですが、律儀に各項の桁数を数えていくと結構時間がかかります。
 Haskell の Integer 型は桁数に制限がないので、コードでは "limit" に 1000 桁の数のうち一番小さい "10 ^ (1000 - 1)" を入れておいて、数字どうしの大小を直接比べるようにしました。

« Project Euler : Problem 24 ~ 順列 | トップページ | Project Euler : Problem 26 ~ 循環節の長さ »

Haskell」カテゴリの記事

Project Euler」カテゴリの記事

コメント

コメントを書く

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

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

トラックバック

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

この記事へのトラックバック一覧です: Project Euler : Problem 25:

« Project Euler : Problem 24 ~ 順列 | トップページ | Project Euler : Problem 26 ~ 循環節の長さ »

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            
フォト

最近のトラックバック

無料ブログはココログ