読者です 読者をやめる 読者になる 読者になる

何かを書き留める何か

数学や読んだ本について書く何かです。最近は社会人として生き残りの術を学ぶ日々です。

Project Euler Problem 9

A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,

a^2 + b^2 = c^2

For example, 3^2 + 4^2 = 9 + 16 = 25 = 5^2

There exists exactly one Pythagorean triplet for which a + b + c = 1000.

Find the product abc

http://projecteuler.net/problem=9.

 

和が1000となるPythagoras数の組を求め、その積を計算する問題。

素直に書くとこうなるだろうか:

----

print [a*b*c for a in xrange(1,1000) for b in xrange(1,1000) for c in xrange(1,1000) \

if a**2 + b**2 == c**2 and a+b+c == 1000]

----

これでも十分計算できるが、for文が3つもあるので結構時間がかかる。

ここでa+b+c =1000という性質を利用する。変数消去という受験でおなじみの常套手段である。c = 1000-(a+b) としてa^2 + b^2 = c^2に代入して整理すると

2(a-1000)(b-1000) = 1000^2

となる。

それを踏まえたソースは以下のようになる:

----

print = [[a,b,1000-(a+b)] for a in xrange(1,1000) for b in xrange(1,1000) \
       if 2*(a-pow(10,3))*(b-pow(10,3)) == pow(10,6) and a < b]

----

 

"exactly one" であるのにリストを用いるのは冗長だろうか。