Magicode logo
Magicode
0

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

問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のみ可

考え方

計算すればいい


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]

25164150

末筆ながら

ご意見求む!!

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

一般項があるはず

Haskellerさんへ

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

スキル指標

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

読んだ本

  • すごいH本
  • 関数プログラミング実践入門 (途中)

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

Discussion

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