« Project Euler : Problem 8 | トップページ | Project Euler : Problem 10 〜 200万以下の素数の和 »

2009年12月27日 (日)

Project Euler : Problem 9 〜 ピタゴラス数

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

 

 一番簡単な方法は、リスト内包表記を使って組み合わせを見つけることだと思います。
 a + b + c = n かつ a < b < c という条件から 0 < a < (n/3), a < b < (n/2) ということが分かるので、これを利用して、探索範囲をちょっとだけ絞り込みました。

-- Brute force pythagoreanNums :: Integral a => a -> [(a, a, a)] pythagoreanNums n = [(a, b, c) | a <- [1 .. div n 3], b <- [a + 1 .. div n 2], c <- [n - a - b], a ^ 2 + b ^ 2 == c ^ 2] problem009 :: Integral a => a -> a problem009 n = a * b * c where (a, b, c) = head $ pythagoreanNums n main = print $ problem009 1000
 最適化オプションを付けてコンパイルすると、約 0.06 秒で答えが出ました。
 しかしこの解き方では、a と b の二つの変数を二重ループにして条件に合う組み合わせを探すので、答えが出るまでに時間がかかります。

 以前 Ruby でこの問題を解いたときにも使った方法では、さらに速く答えが出せます。(詳しい解説はこちらをご覧ください)

-- ピタゴラス数 -- a + b + c = n, a^2 + b^2 = c^2, a < b < c の組を探す。 pythagoreanNums :: Integral a => a -> [(a, a, a)] pythagoreanNums n | odd n = [] | otherwise = [(a, b, n - a - b) | a <- [1 .. div n 3], check a, b <- [calc a], a < b] where check a = rem (a * n) (2 * (n - a)) == 0 calc a = div (n * (n - 2 * a)) (2 * (n - a)) problem009 :: Integral a => a -> a problem009 n = a * b * c where (a, b, c) = head $ pythagoreanNums n main = print $ problem009 1000
 これだと、実際に動かす変数は a の一つだけなので、約 0.005 秒で答えが出ます。

« Project Euler : Problem 8 | トップページ | Project Euler : Problem 10 〜 200万以下の素数の和 »

Haskell」カテゴリの記事

Project Euler」カテゴリの記事

コメント

コメントを書く

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

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

トラックバック

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

この記事へのトラックバック一覧です: Project Euler : Problem 9 〜 ピタゴラス数:

« Project Euler : Problem 8 | トップページ | Project Euler : Problem 10 〜 200万以下の素数の和 »

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

最近のトラックバック

無料ブログはココログ