« あなたの「干支」は何ですか? | トップページ | Project Euler : Problem 55 »

2010年11月 4日 (木)

Project Euler : Problem 53 その2

 問題はこちらをご覧ください。
 また、自作の "ForEuler module" に関してはこちらをご覧ください。

 

 前回 "Problem 53" の記事を投稿した後、同じ問題を解いていらっしゃる他の方々のブログを眺めていたら、なぜか「パスカルの三角形」の単語がちょくちょく出てきました。
 最初は「??」だったのですが、「『組み合わせ』といえば『パスカルの三角形』」ということをやっと思いだしました。(分らない人は "Wikipedia" などで調べて見てください)
 それで、急いで自分なりの「パスカルの三角形バージョン」を作ってみました。

pascal'sTriangle :: [[Integer]] pascal'sTriangle = iterate func [1] where func ns = zipWith (+) (0:ns) ns ++ [1] -- nCr > m となる r の数 count :: [Integer] -> Integer -> Int count ns m = if r == length ns then 0 else length ns - 2 * r where r = length $ takeWhile (<= m) ns problem053 :: Int problem053 = sum $ map (`count` 1000000) $ take 101 pascal'sTriangle main :: IO () main = print problem053

 「パスカルの三角形」を使ってこの問題を解くと、階乗の計算が不要になるのでかなり速く解けますね。

« あなたの「干支」は何ですか? | トップページ | Project Euler : Problem 55 »

Haskell」カテゴリの記事

Project Euler」カテゴリの記事

コメント

コメントを書く

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

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

トラックバック

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

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

« あなたの「干支」は何ですか? | トップページ | Project Euler : Problem 55 »

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

最近のトラックバック

無料ブログはココログ