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

2010年10月29日 (金)

Project Euler : Problem 53

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

 

 まずは、brute force 版。何も考えず、問題を素直に解きました。

import ForEuler problem053 :: Int problem053 = length $ filter (> 1000000) combs where combs = [combinationSize n r | n <- [1 .. 100], r <- [1 .. n]] main :: IO () main = print problem053
 これでも、最適化オプションを付けてコンパイルすれば、うちの非力なノートパソコンでも約 0.1 秒ほどで答えが出ます。

 ここで一工夫。
 先ほどのコードでは、"combinationSizse 関数" の内部で階乗の計算が繰り返し行われています。そこで階乗の計算結果をメモ化してみました。

import Data.Array factorial :: Integer -> Integer factorial n = facts ! n where facts = listArray (0, 100) (1 : [factorial' x | x <- [1 .. 100]]) factorial' x = x * factorial (x - 1) combSize :: Integer -> Integer -> Integer combSize n r = div (factorial n) (factorial r * factorial (n - r)) problem053 :: Int problem053 = length $ filter (> 1000000) combs where combs = [combSize n r | n <- [1 .. 100], r <- [1 .. n]] main :: IO () main = print problem053
 これだと計算の無駄な繰り返しが無くなるので、うちのパソコンで約 0.03 秒で答えが出ます。かなり高速化されました。

 今度はちょっと考え方を変えてみます。
 次の結果を見てください。

> map (combinationSize 10) [0..10] > [1,10,45,120,210,252,210,120,45,10,1]
 組み合わせの式の定義からも分かることですが、nCr = nC(n-r) が成り立ちます。
 また、r が n/2 に達するまでは nCr は大きくなっていき、r が n/2 を越えると対照的に小さくなっていきます。
 このことから、r を 0 から小さい順に調べていって、nCr0 が初めて 1000000 を越えた場合、r0 ≦ r ≦ (n - r0) の範囲にある r では、必ず nCr > 1000000 が成立します。
 ということは、特定の n に対する r0 さえ見つけてしまえば、nCr > 1000000 が成立する場合の数が分かることになります。
import ForEuler -- nCr > m となる r の数 count :: Integer -> Integer -> Integer count n m = if null rs then 0 else n - 2 * (head rs) + 1 where -- rs : nCr > m となる r の集合の前半 rs = filter (\x -> combinationSize n x > m) [0 .. (div n 2)] problem053 :: Integer problem053 = sum $ map (`count` 1000000) [1 .. 100] main :: IO () main = print problem053
 今回は計算量が少ないので、階乗の計算をメモ化しなくても十分速いです。うちのパソコンで約 0.01 秒で答えが出ました。

 Project Euler って、コーディングの知識も要求されるけど、うまい解法を見つけることがもっと重要かも……。

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

Haskell」カテゴリの記事

Project Euler」カテゴリの記事

コメント

コメントを書く

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

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

トラックバック

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

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

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

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

最近のトラックバック

無料ブログはココログ