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

【和の2乗-2乗の和】一緒に考えませんか？ #Project Euler

問6

(1+2+..+10)^2 - (1^2 + 2^2 + .. + 10^2) = 2640

1～100の場合は？

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

計算すればいい

sum [1..100] ^ 2 - foldl1 (\acc x -> acc + x^2) [1..100]

25164150

ちょっと面白くないので別解を考えてみる

(a + b + c + d)^2 = a^2 + b^2 + c^2 + d^2 + a(b+c+d) + b(a+c+d) + c(a+b+d) + d(a+b+c)

= a^2 + b^2 + c^2 + d^2 + 2(ab + ac + ad + bc + bd + cd)

= a^2 + b^2 + c^2 + d^2 + 2(a(b + c + d) + b (c + d) + c(d))

つまり

(a + b + c + d)^2 - (a^2 + b^2 + c^2 + d^2) = 2(a(b + c + d) + b (c + d) + c(d))

具体的な数値を与えてみる

(1 + 2 + 3 + 4)^2 = 2( 1(2 + 3 + 4) + 2(3 + 4) + 3(4) )

x * [x+1..4]の和 (x: 1～4)を2倍しているように見えてくる

2 * foldl (\acc x -> acc + (x * sum [x+1..100])) 0 [1..100]

毎回リストを走査するのがもったいない？

2 * fst $ foldl (\(ans, total) x -> (ans + x * total, total + x)) (0, 0) [100,99..0]

2 * fst (foldl (\(ans, total) x -> (ans + x * total, total + x)) (0, 0) [100,99..0])

25164150

2個目の回答は効率が良くなっているのか？

一般項があるはず

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

実務1年程度のへっぽこプログラマーなので暖かくも厳しく見守ってください

読んだ本

つまり構文を知った程度で、関数型言語っぽい書き方を学び中です

Ads