・0 pv・2 min read
【回分数】一緒に考えませんか？ #Project Euler
考え方
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 orderJust (993,913)
末筆ながら
ご意見求む!!
もっと簡単にかけ算の降順リストを作れそう (命令型感が否めない)
パリンドローム -> かけ算 のやり方で綺麗に解く方法
Haskellerさんへ
計算量, 見やすさ, 文化的な観点から見て改善点や他回答があればぜひお願いします！
スキル指標
実務1年程度のへっぽこプログラマーなので暖かくも厳しく見守ってください
読んだ本
- すごいH本
- 関数プログラミング実践入門 (途中)
つまり構文を知った程度で、関数型言語っぽい書き方を学び中です