« Project euler : Problem 3 ~ 素因数分解 | トップページ | Project Euler : Problem 5 ~ 最小公倍数 »

2009年12月14日 (月)

Project Euler : Problem 4 ~ 回文数

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

 一番簡単な方法は、すべての 3 桁の数の積を求めていく方法だと思います。

-- 回文数か? isPalindromic :: Show a => a -> Bool isPalindromic n = str == reverse str where str = show n problem004 :: Integer problem004 = maximum [x | x <- prod, isPalindromic x] where prod = [y * z | y <- [100 .. 999], z <- [y .. 999]] main = print problem004

 しかし、この方法では計算量が多いため、時間がかかります。
 コンパイルして実行した場合、私のパソコンでは次のようになりました。

real 0m0.224s user 0m0.188s sys 0m0.008s

 以前、Ruby 版のコードを載せた記事にも書いたのですが、実際に求めるのは最大値だけなので、「3 桁の数の積を求めるための二重ループを作るときに、大きい数から積を求めていって、その時点で分かっている回文数の最大値より積の数が小さくなったらそれ以上計算をしない」という方法をとると、計算量が減らせるのでかなりのスピードアップが望めます。
 そこで、自分が以前書いた Ruby 版や Scheme 版を基にして Haskell 版のコードを書こうとしたのですが、積を求めるための二重ループをどうやって関数の形にするかで結構苦労しました。

-- 回文数か? isPalindromic :: Show a => a -> Bool isPalindromic n = str == reverse str where str = show n nss :: [[Int]] nss = map prd [999, 998 .. 100] where prd x = [x * y | y <- [x, x - 1 .. 100]] problem004 :: Int problem004 = foldl findMax 0 nss where -- その時点の最大値より小さい値は調べない findMax m ns | null ns' = m | otherwise = max m (head ns') where ns' = filter isPalindromic $ takeWhile (> m) ns main = print problem004

 このコードをコンパイルして実行すると、

real 0m0.013s user 0m0.012s sys 0m0.000s
という結果になりました。最初のコードの約 14 倍のスピードです。

 さらに、ちょっと違う視点からの解法を考えてみます。
 それは「まず、大きい順に回文数を作っていき、3 桁の数の積に分解できるものを探す」という方法です。
 999 x 999 = 998001 なので、997799 以下の回文数を探せばいいことになります。

-- 奇数桁の回文数を作る oddPalNum :: Int -> Int oddPalNum n = read (ns ++ tail (reverse ns)) where ns = show n -- 偶数桁の回文数を作る evenPalNum :: Int -> Int evenPalNum n = read (ns ++ reverse ns) where ns = show n -- 3 桁 * 3 桁に分解できるか? findDivs :: Int -> Bool findDivs n = not $ null ns where isqrt = truncate . sqrt . fromIntegral ns = [x | x <- [isqrt n, isqrt n - 1 .. 100], rem n x == 0, div n x >= 100, div n x <= 999] problem004 :: Int problem004 = head [x | x <- pals1 ++ pals2, findDivs x] where pals1 = map evenPalNum [997, 996 .. 100] pals2 = map oddPalNum [997, 996 .. 100] main = print problem004

 Project Euler は同じ問題でもアプローチの仕方を変えるといろいろな解法が考えられるので、一つの問題でいろいろなコードを書くことができます。
 コードを書く練習としてはなかなか良いのでは?と思います。

追記 (2010/05/16):以前書いたコードが冗長に思えたので、一部書き直しました。

« Project euler : Problem 3 ~ 素因数分解 | トップページ | Project Euler : Problem 5 ~ 最小公倍数 »

Haskell」カテゴリの記事

Project Euler」カテゴリの記事

コメント

コメントを書く

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

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

トラックバック

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

この記事へのトラックバック一覧です: Project Euler : Problem 4 ~ 回文数:

« Project euler : Problem 3 ~ 素因数分解 | トップページ | Project Euler : Problem 5 ~ 最小公倍数 »

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

最近のトラックバック

無料ブログはココログ