Ccmmutty logo
Commutty IT
0 pv2 min read

【回分数】一緒に考えませんか? #Project 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)
haskell
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

Just (993,913)

末筆ながら

ご意見求む!!

もっと簡単にかけ算の降順リストを作れそう (命令型感が否めない)
パリンドローム -> かけ算 のやり方で綺麗に解く方法

Haskellerさんへ

計算量, 見やすさ, 文化的な観点から見て改善点や他回答があればぜひお願いします!

スキル指標

実務1年程度のへっぽこプログラマーなので暖かくも厳しく見守ってください
読んだ本
  • すごいH本
  • 関数プログラミング実践入門 (途中)
つまり構文を知った程度で、関数型言語っぽい書き方を学び中です

Discussion

コメントにはログインが必要です。