Ccmmutty logo
Commutty IT
0 pv2 min read

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

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

問6

(1+2+..+10)2(12+22+..+102)=2640(1+2+..+10)^2 - (1^2 + 2^2 + .. + 10^2) = 2640
1~100の場合は?
Project Euler ※解法の公開は問1~100のみ可

考え方

計算すればいい
haskell
sum [1..100] ^ 2 - foldl1 (\acc x -> acc + x^2) [1..100]

25164150

考え方2

ちょっと面白くないので別解を考えてみる
(a+b+c+d)2=a2+b2+c2+d2+a(b+c+d)+b(a+c+d)+c(a+b+d)+d(a+b+c)(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)
=a2+b2+c2+d2+2(ab+ac+ad+bc+bd+cd)= a^2 + b^2 + c^2 + d^2 + 2(ab + ac + ad + bc + bd + cd)
=a2+b2+c2+d2+2(a(b+c+d)+b(c+d)+c(d))= a^2 + b^2 + c^2 + d^2 + 2(a(b + c + d) + b (c + d) + c(d))
つまり
(a+b+c+d)2(a2+b2+c2+d2)=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))(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]
haskell
2 * fst (foldl (\(ans, total) x -> (ans + x * total, total + x)) (0, 0) [100,99..0])

25164150

末筆ながら

ご意見求む!!

2個目の回答は効率が良くなっているのか?
一般項があるはず

Haskellerさんへ

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

スキル指標

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

Discussion

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