24か月前公開・24か月前更新・2 min read

【回分数】一緒に考えませんか？ #Project Euler

アルゴリズムHaskellProject Euler

https://cdn.magicode.io/media/notebox/DSC_00281_jy1yWRX.jpg

問4

9009 = 90 * 99 が2桁同士のかけ算での最大回文数

3桁同士だと？

Project Euler ※解法の公開は問1～100のみ可

考え方

6桁のパリンドロームを乗算に分解するのは素数で試し割りをするので計算量が多くなりそう

かけ算を999 * 999から試していき最初にパリンドロームになった値を答えとする方法をとる

x * y の組み合わせで値が大きい順にするには(x + y)が大きく|x - y|が小さい順にすればいい

かけ算降順

order :: [(Int, Int)]
order = (999, 999) : (999, 998) : (998, 998) : (999, 997) : ...  のようにリストを構築したい

ひとつ前の値を見て次の値を作るというような再帰的な定義で考えてみる

order = (999, 999) : map next order

ある和(a+b)での絶対値が最小のペア (a, b) -> 次に小さいペア (a+1, b-1) -> ..

-> (桁数が変わってしまったら) (a+b-1)での絶対値が最小のペア (a2, b2) -> 次に小さいペア (a2+1, b2-1) -> ..

のようになればいい

next :: (Int, Int) -> (Int, Int)
next (a, b)
    | a < 999 && b > 100 = (succ a, pred b) 
    | otherwise = let dec = (a+b-1) in (dec `div` 2 + dec `mod` 2, dec `div` 2)

回文数かどうかを判定

中身はどういう風でもいいので単純に反対にした値と一致するかを判定することにする

isPalindrome :: (Int, Int) -> Bool
isPalindrome (a, b) = a * b == (read . reverse . show) (a * b)

import Data.List

order :: [(Int, Int)]
order = (999, 999) : map next order
next :: (Int, Int) -> (Int, Int)
next (a, b)
    | a < 999 && b > 100 = (succ a, pred b)
    | otherwise = let dec = (a+b-1) in (dec `div` 2 + dec `mod` 2, dec `div` 2)

isPalindrome :: (Int, Int) -> Bool
isPalindrome (a, b) = a * b == (read . reverse . show) (a * b)

print $ find isPalindrome order