« Project Euler : Problem 11 | トップページ | Project Euler : Problem 12 ~ 三角数の約数の数 (2) »

2010年1月 7日 (木)

Project Euler : Problem 12 ~ 三角数の約数の数 (1)

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

 

 今回は三角数の数列の問題です。
 問題では「三角数は自然数の和の形で表わせる」と説明されています。これを基に三角数を定義すると

triNum :: Integral a => a -> a triNum n = div ((1 + n) * n) 2
ということになります。
 しかし今回は、私が作った多角数の無限リストを返す関数を使います。
-- 多角数のリスト polyNumList :: Integral a => a -> [a] polyNumList n = poly 1 (n - 1) (n - 2) where poly v add d = v : poly (v + add) (add + d) d
 例えば n を 3 にすると三角数の無限リストを返します。
*Main> take 10 $ polyNumList 3 [1,3,6,10,15,21,28,36,45,55]

 約数の個数は、実際の約数を調べなくても、素因数分解の結果を利用すると簡単に出せます。

-- 約数の個数 numOfDivs :: Integral a => a -> Int numOfDivs n = product [b + 1 | (_, b) <- factorize n]

 これらをまとめると、次のようになりました。

import Data.List (group) -- 素因数分解 (要 : priems) factorize :: Integer -> [(Integer, Int)] factorize 1 = [(1, 0)] factorize n = format $ factorize' n divs where factorize' n xs'@(x : xs) | n < x * x = [n] | rem n x == 0 = x : factorize' (div n x) xs' | otherwise = factorize' n xs format xss = [(head xs, length xs) | xs <- group xss] divs :: [Integer] divs = 2 : 3 : [x + y | x <- [6, 12 ..], y <- [-1, 1]] -- 約数の個数 numOfDivs :: Integer -> Int numOfDivs n = product [b + 1 | (_, b) <- factorize n] -- 多角数のリスト polyNumList :: Integer -> [Integer] polyNumList n = poly 1 (n - 1) (n - 2) where poly v add d = v : poly (v + add) (add + d) d problem012 :: Integer problem012 = head $ dropWhile ((<= 500) . numOfDivs) triNums where triNums = polyNumList 3 main = print problem012

 最適化オプションを付けてコンパイルしたものを、 Pentium M, 1500MHz のノートパソコンで実行すると、約 0.15 秒で答えが出ました。

 今回の方法でもそこそこ速いのですが、実はもっと速く答えが出せるやり方があります(同じノートパソコンで約 0.05 秒)。
 その具体的な方法は、次回ということで……。

 

追記:
 rst76 さんのところで、素因数分解のコードの「Haskell っぽいコードってどんなだろう」という話題が出ていました。
 rst76 さんは「高階関数」を挙げていらっしゃいますが、私自身は以前、Scheme をいじっていたので、「高階関数」は普通に使っていたしなあ……。
 ということで、Haskell 初心者の私が Ruby や Scheme のコードを書く場合と比べて考えるに、「if の使用頻度」と「リスト内包表記」かなと思います。
 Haskell のコードを書くときには、「パターンマッチ」や「ガード」が便利過ぎて、関数定義をする際に if を使う機会がめっきり減りました。
 しかも、「パターンマッチ」、「ガード」、「リスト内包表記」を使うとすっきりして見やすくなるような気がするので、つい多用してしまいます。

« Project Euler : Problem 11 | トップページ | Project Euler : Problem 12 ~ 三角数の約数の数 (2) »

Haskell」カテゴリの記事

Project Euler」カテゴリの記事

コメント

コメントを書く

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

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

トラックバック

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

この記事へのトラックバック一覧です: Project Euler : Problem 12 ~ 三角数の約数の数 (1):

« Project Euler : Problem 11 | トップページ | Project Euler : Problem 12 ~ 三角数の約数の数 (2) »

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

最近のトラックバック

無料ブログはココログ