« Project Euler : Problem 43 | トップページ | Project Euler : Problem 45 ~ 三角数、五角数、六角数 »

2010年8月19日 (木)

Project Euler : Problem 44 ~ 五角数

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

 

 Ruby 版と同じ方法で解いてみました。

import ForEuler (polyNumList, isPolyNum) import Data.List (find) import Maybe (isNothing, fromJust) pentagonList :: [Integer] pentagonList = polyNumList 5 isPentagon :: Integer -> Bool isPentagon = isPolyNum 5 problem044 :: Integer problem044 = loop (tail pentagonList) [1] where loop (p : ps) pent | isNothing a = loop ps (p : pent) | otherwise = p - fromJust a where a = find check pent check p' = all isPentagon [p - p', p + p'] main :: IO () main = print problem044
 これが遅い!コンパイルして実行すると、私のノートパソコンで約 8 秒かかりました。いわゆる 1 分ルールには引っかからないのですが、Ruby 版より遅い……。
 リスト操作のコストが高いのでしょうか?それとも「find 関数」のコストが高いのが原因でしょうか?

 他の方法を自分でもいろいろ考えたのですが、いい方法を思いつきませんでした。
 そこで、ネットを探したところ、こちらのブログにいい方法が書いてありました。自分も、式の変形を使って解けないかと考えたこともあったのですが、この解法までたどり着けませんでした。
 ということで、こちらの解法を参考にコードを書いてみました。

import ForEuler (polyNumList, polyNum, isPolyNum, divisor) import Data.List (find) pentagonList :: [Integer] pentagonList = polyNumList 5 pentagon :: Integer -> Integer pentagon = polyNum 5 isPentagon :: Integer -> Bool isPentagon = isPolyNum 5 divsPair :: Integer -> [(Integer, Integer)] divsPair n = takeWhile (\ (a, b) -> a <= b) $ zip ds (reverse ds) where ds = divisor n mn :: Integer -> [(Integer, Integer)] mn k = [(div (a + c) 2, div (c - a) 2) | (a, b) <- divsPair (2 * k), rem b 3 == 2, let c = div (b + 1) 3, a < c] probrem044 :: Integer probrem044 = pentagon m - pentagon n where Just (m, n) = find check $ concatMap mn $ pentagonList check (m, n) = isPentagon (pentagon m + pentagon n) main :: IO () main = print probrem044
 こちらの方法では、コンパイルして実行すると約 0.17 秒で答えが出ました。あまりの違いにビックリしてしまいました。

« Project Euler : Problem 43 | トップページ | Project Euler : Problem 45 ~ 三角数、五角数、六角数 »

Haskell」カテゴリの記事

Project Euler」カテゴリの記事

コメント

コメントを書く

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

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

トラックバック

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

この記事へのトラックバック一覧です: Project Euler : Problem 44 ~ 五角数:

« Project Euler : Problem 43 | トップページ | Project Euler : Problem 45 ~ 三角数、五角数、六角数 »

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

最近のトラックバック

無料ブログはココログ